Cristopher Moore Santa Fe Institute
Defn. Let $x \in{+1,-1}^n$ be uniformly random, and let $Y$ be a noisy version of the rank-one tensor consisting of the $p$th tensor power of $x$, namely $Y = \lambda x^{\otimes p} + W$. Here $W$ is a noise tensor whose entries are independent Gaussians with mean $0$ and variance $1$ except that $W$ is symmetric, and $\lambda$ is a signal-to-noise ratio. (The asymmetric version where $Y = \lambda x_1 \otimes x_2 \otimes \cdots \otimes x_p + W$ is equally interesting.)
Problem. If $\lambda \gg n^{(1-p)/2}$ it is information-theoretically possible to approximately recover $x$ from $Y$, i.e., to find a vector $\hat{x}$ that agrees with $x$ at a fraction of coordinates bounded above $1/2$. We know of polynomial-time algorithms that do this whenever $\lambda \gg n^{p/4}$. These two thresholds coincide when $p=2$, where $Y$ is a random matrix with a rank-one perturbation, but when $p \ge 3$ there is a gap between them. We believe that between these two thresholds, approximate recovery is possible but takes exponential time. Can you find any evidence for or against this conjecture?
Additional Questions?
If you have additional questions, feel free to reach out to a maintainer / contributor on the contact page.
