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 X^★ 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 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 Alt-PGD-Min achieves ϵ-accuracy recovery with O (κ² log ¹_ϵ ) iteration complexity and O (κ⁶rn3 log n3 (κ²r (n1 + n2) + n1 log ¹_ϵ⁾⁾ sample complexity, where κ denotes tensor condition number of X^★. To further accelerate the convergence, especially when the tensor is ill-conditioned with large κ, we prove AltScalePGD-Min that preconditions the gradient update using an approximate Hessian that can be computed efficiently. We show that Alt-ScalePGD-Min achieves κ independent iteration complexity O(log ¹_ϵ) and improves the sample complexity to O (κ⁴rn3 log n3 (κ⁴r(n1 + n2) + n1 log ¹_ϵ⁾⁾. Experiments validate the effectiveness of the proposed methods.