Non-Convex Tensor Recovery from Local Measurements

Motivated by the settings where sensing the entire tensor is infeasible, this paper proposes a novel tensor compressed sensing model, where measurements are only obtained from sensing each lateral slice via mutually independent matrices. Leveraging the low tubal rank structure, we reparameterize the unknown tensor ${\mathcal{X}}^{\star }$ using two compact tensor factors and formulate the recovery problem as a nonconvex minimization problem. To solve the problem, we first propose an alternating minimization algorithm, termed $\mathsf{\text{Alt-PGD-Min}}$, that iteratively optimizes the two factors using a projected gradient descent and an exact minimization step, respectively. Despite nonconvexity, we prove that $\mathsf{\text{Alt-PGD-Min}}$ achieves $\epsilon$-accuracy recovery with $\mathcal{O}({\kappa }^2\log \frac{1}{\epsilon })$ iteration complexity and $\mathcal{O}({\kappa }^{6}r{n}_3\log n_3({\kappa }^{2}r(n_1+n_2)+n_1\log \frac{1}{\epsilon }))$ sample complexity, where $\kappa$ denotes tensor condition number of ${\mathcal{X}}^{\star }$. To further accelerate the convergence, especially when the tensor is ill-conditioned with large $\kappa$, we prove $\mathsf{\text{Alt-ScalePGD-Min}}$ that preconditions the gradient update using an approximate Hessian that can be computed efficiently. We show that $\mathsf{\text{Alt-ScalePGD-Min}}$ achieves $\kappa$ independent iteration complexity $\mathcal{O}(\log \frac{1}{\epsilon })$ and improves the sample complexity to $\mathcal{O}({\kappa }^{4}r{n}_3\log n_3({\kappa }^{4}r(n_1+n_2)+n_1\log \frac{1}{\epsilon }))$. Experiments validate the effectiveness of the proposed methods.