Non-Convex Tensor Recovery from Local Measurements

Abstract

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( ^2 1) iteration complexity and O( ^6rn_3 n_3 ( ^2r(n_1 + n_2 ) + n_1 1) ) 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 Alt-ScalePGD-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( 1) and improves the sample complexity to O( ^4 rn_3 n_3 ( ^4r(n_1+n_2) + n_1 1) ). Experiments validate the effectiveness of the proposed methods.

Tasks

Reproductions