Square Deal: Lower Bounds and Improved Relaxations for Tensor Recovery

By Cun Mu, Bo Huang, John Wright, Donald Goldfarb. International Conference on Machine Learning, 2013

327 citations recorded by the source corpus.

Recovering a low-rank tensor from incomplete information is a recurring problem in signal processing and machine learning. The most popular convex relaxation of this problem minimizes the sum of the nuclear norms (SNN) of the unfolding matrices of the tensor. We show that this approach can be substantially suboptimal: reliably recovering a K-way n×n×...×n tensor of Tucker rank (r, r,..., r) from Gaussian measurements requires Ω(rnK-1) observations. In contrast, a certain (intractable) nonconvex formulation needs only O(rK+nrK) observations. We introduce a simple, new convex relaxation, which partially bridges this gap. Our new formulation succeeds with O(r⌊K/2⌋n⌈K/2⌉) observations. The lower bound for the SNN model follows from our new result on recovering signals with multiple structures (e.g. sparse, low rank), which indicates the significant suboptimality of the common approach of minimizing the sum of individual sparsity inducing norms (e.g. l1, nuclear norm). Our new tractable formulation for low-rank tensor recovery shows how the sample complexity can be reduced by designing convex regularizers that exploit several structures jointly.

Subfields: Aerospace Engineering, Computational Mathematics, Computational Mechanics

View Paper: https://www.semanticscholar.org/paper/28e23424e5143fa016268dc7530433a9b27fb959

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Aerospace Engineering

In Computational Mathematics

In Computational Mechanics

Citations in the corpus

Low-Rank Tensor Learning with Discriminant Analysis for Action Classification and Image Recovery (2014, background): “…representation learning approaches have been proposed (Chen and Saad 2009; Koch and Lubich 2010; Haegeman et al. 2011; Holtz, Rohwedder, and Schneider 2012; Khoromskij, Oseledets, and Schneider 2012; Arnold and Jahnke 2012; Lubich et al. 2013; Uschmajew and Vandereycken 2013; Mu et al. 2013).”
Rubik: Knowledge Guided Tensor Factorization and Completion for Health Data Analytics (2015, background): “A number of other alternatives have also been discussed in [20, 24, 28].”
Low-rank tensor completion by Riemannian optimization (2014, background): “Besides the two approaches described above, a number of variations [20] and alternatives have been discussed in the literature.”
Tensor Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Tensors via Convex Optimization (2016, background): “The work [21] further proposes a better convexification based on a more balanced matricization of X and improves the bound to O(rb k 2 cnb k 2 c).”
Tensor Robust Principal Component Analysis with a New Tensor Nuclear Norm (2018, methodology): “Actually, the above model can be substantially suboptimal [24]: reliably recovering a k -way tensor of length n and Tucker rank ( r, r, · · · , r ) from Gaussian measurements requires O ( rn k − 1 ) observations.”
Parallel matrix factorization for low-rank tensor completion (2013, unknown): “The recent work [18] proposes a more “square” convex model for recovering M as follows: (6) min where ˆ Z ∈ R I i 1 × ... × I iN is a tensor by relabeling mode i n of Z to mode n for n = 1 , . . . , N , and j and the permutation ( i 1 , . . . , i N ) are chosen to make n ≤ j I i n as close as to…”
Exact Tensor Completion Using t-SVD (2015, methodology): “3) Tensor Completion Under Gaussian Measurements: Instead of random sampling, in [23] a different method for low CP or Tucker rank tensor completion under Gaussian measurements is proposed.”
Efficient Tensor Completion for Color Image and Video Recovery: Low-Rank Tensor Train (2016, methodology): “2: While not converged do: Unfold the tensor X l to get X l [ k ] 5: ) 6: end for 7: Update X l +1 from M l +1 k by (30) 8: End while Output: The recovered tensor X as an approximation of T”
Tensor Factorization for Low-Rank Tensor Completion (2018, methodology): “Since t-SVD is based on an operator theoretic interpretation of 3-way tensors as linear operators on the space of oriented matrices, the tensor multi-rank and tubal rank can well characterize the inherent low-rank structure of a tensor while avoiding the loss of information inherent in matricization”