12 problems

Let $k$ be the order of a tensor, and consider noisy tensor completion for an order-$k$ tensor of dimension parameter $n$. A polynomial-time algorithm is an algorithm whose running…

For a third-order tensor completion problem with sampling complexity measured by the number of observed entries $pn_1n_2n_3$, the relevant regime is $\mu=O(1)$ and…

Let $\mathcal{T}$ be a tensor whose mode-1 unfolding $\mathcal{T}_{(1)}$ is observed on $\Omega_{\mathcal{T}}$, let $M$ be a matrix observed on $\Omega_M$, and let $G$ be the unkno…

Tensor robust PCA recovery conjecture. The factor

Polynomial-time tensor completion conjecture. No polynomial-time algorithm will be successful if the sample complexity is less than order $n^{3/2}$.

Let $\operatorname{Seg}(n_1,\ldots,n_k)$ denote the Segre variety with parameters $(n_1,\ldots,n_k)$, and let $d$-defectivity mean that its $d$-secant variety has smaller than the…

Let $A$ be the observed matrix associated with a tensor-completion problem, let $M$ denote the underlying signal matrix, and let $B$ be the matrix whose eigenvectors are embedded i…

Consider completion of a third-order tensor of dimension $d$ and rank $r$, using polynomial-time algorithms. SOS sample-complexity conjecture. The sample complexity achieved by SOS…

Let $\bm{T}^{\star} \in \mathbb{R}^{d\times d\times d}$ be a rank-$r$ symmetric tensor of the form … where each $\bm{u}_i^{\star}\in\mathbb{R}^d$, and suppose that entries are obse…

3-XOR distinguishing hardness conjecture. There is some constant $\eta<1/4$ such that no algorithm that succeeds for the 3-XOR distinguishing problem with $m=o(d^{3/2})$ runs in po…

A measurement map ${\mathcal A}:\mathcal H_d\to\mathbb R^m$ is called Gaussian when its entries are independent normal random variables with mean zero and variance $1/m$. For a hie…

Let a third-order tensor have a t-SVD with f-diagonal tensor $\boldsymbol{\mathscr{S}}$, and define its tensor-tubal-rank as the number of nonzero diagonal tubes…