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 boldsymbol 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 textsfAlt-PGD-Min, that iteratively optimizes the two factors using a projected gradient descent and an exact minimization step, respectively. Despite nonconvexity, we prove that textsfAlt-PGD-Min achieves ε-accuracy recovery with mathcal Oleft( kappa2 log frac1εright) iteration complexity and mathcal Oleft( kappa6rn3log n3 left( kappa2rleft(n1 + n2 right) + n1 log frac1εright) right) sample complexity, where kappa denotes tensor condition number of boldsymbolmathcal X^star. To further accelerate the convergence, especially when the tensor is ill-conditioned with large kappa, we prove textsfAlt-ScalePGD-Min that preconditions the gradient update using an approximate Hessian that can be computed efficiently. We show that textsfAlt-ScalePGD-Min achieves kappa independent iteration complexity mathcal O(log frac1ε) and improves the sample complexity to mathcal Oleft( kappa4 rn3 log n3 left( kappa4r(n1+n2) + n1 log frac1εright) right). Experiments validate the effectiveness of the proposed methods.