Tensor theta norms and low rank recovery
From MaRDI portal
Publication:2048814
compressive sensingconvex relaxationGröbner baseslow rank tensor recoverypolynomial idealssemidefinite programmingtensor nuclear normtheta bodies
Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60) Multilinear algebra, tensor calculus (15A69) Convex functions and convex programs in convex geometry (52A41) Semidefinite programming (90C22) Convex programming (90C25) Sampling theory in information and communication theory (94A20)
Abstract: We study extensions of compressive sensing and low rank matrix recovery to the recovery of low rank tensors from incomplete linear information. While the reconstruction of low rank matrices via nuclear norm minimization is rather well-understand by now, almost no theory is available for the extension to higher order tensors due to various theoretical and computational difficulties arising for tensor decompositions. In fact, nuclear norm minimization for matrix recovery is a tractable convex relaxation approach, but the extension of the nuclear norm to tensors is in general NP-hard to compute. In this article, we introduce convex relaxations of the tensor nuclear norm which are computable in polynomial time via semidefinite programming. Our approach is based on theta bodies, a concept from computational algebraic geometry similar to the Lasserre relaxations. We introduce polynomial ideals which are generated by the second order minors corresponding to different matricizations of the tensor (where the tensor entries are treated as variables) such that the nuclear norm ball is the convex hull of the algebraic variety of the ideal. The -th theta body for such an ideal generates a new norm which we call the -norm. We show that in the matrix case, these norms reduce to the nuclear norm. For tensors of order however, we obtain new norms. The sequence of the corresponding unit--norm balls converges asymptotically to the unit tensor nuclear norm ball. By providing the Gr"obner basis for the ideals, we explicitly give semidefinite programs for the computation of the -norm and for the minimization of the -norm under an affine constraint. Numerical experiments for order-3 tensor recovery via -norm minimization suggest that our approach successfully reconstructs tensors of low rank from incomplete linear (random) measurements.
Recommendations
- Robust low-rank tensor recovery: models and algorithms
- Tensor completion and low-\(n\)-rank tensor recovery via convex optimization
- Low rank tensor recovery via iterative hard thresholding
- Nonconvex tensor rank minimization and its applications to tensor recovery
- Robust Low-Rank Tensor Recovery via Nonconvex Singular Value Minimization
- Low-rank approximation of tensors
- Tensor \(N\)-tubal rank and its convex relaxation for low-rank tensor recovery
- Iterative \(p\)-shrinkage thresholding algorithm for low Tucker rank tensor recovery
- On the Tensor SVD and the Optimal Low Rank Orthogonal Approximation of Tensors
- Singular Value Decompositions and Low Rank Approximations of Tensors
Cites work
- A mathematical introduction to compressive sensing
- A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs
- A Newton-CG augmented Lagrangian method for semidefinite programming
- An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems
- An introduction to hierarchical (\(\mathcal H\)-) rank and TT-rank of tensors with examples
- Bruno Buchberger's PhD thesis 1965: An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal. Translation from the German
- Completing any low-rank matrix, provably
- Compressed sensing
- Exact matrix completion via convex optimization
- Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
- Hierarchical Singular Value Decomposition of Tensors
- scientific article; zbMATH DE number 1716480 (Why is no real title available?)
- scientific article; zbMATH DE number 6474942 (Why is no real title available?)
- scientific article; zbMATH DE number 4067064 (Why is no real title available?)
- scientific article; zbMATH DE number 1796829 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- scientific article; zbMATH DE number 967931 (Why is no real title available?)
- Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra
- Kronecker Compressive Sensing
- Low rank matrix recovery from rank one measurements
- Low rank tensor recovery via iterative hard thresholding
- Low-rank tensor completion by Riemannian optimization
- Moments, positive polynomials and their applications
- Most tensor problems are NP-hard
- Nuclear norm of higher-order tensors
- On tensor completion via nuclear norm minimization
- On the Shannon capacity of a graph
- Phaselift: exact and stable signal recovery from magnitude measurements via convex programming
- Proximal splitting methods in signal processing
- Recovering Low-Rank Matrices From Few Coefficients in Any Basis
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
- Schwartz Spaces, Nuclear Spaces and Tensor Products
- SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints
- Secant varieties of \(\mathbb{P}^{2} \times \mathbb{P}^{n}\) embedded by \(\mathcal O(1,2)\)
- Semidefinite Optimization and Convex Algebraic Geometry
- Simultaneously Structured Models With Application to Sparse and Low-Rank Matrices
- Tensor completion and low-\(n\)-rank tensor recovery via convex optimization
- Tensor completion in hierarchical tensor representations
- Tensor Rank and the Ill-Posedness of the Best Low-Rank Approximation Problem
- Tensor rank is NP-complete
- Tensor spaces and numerical tensor calculus
- Tensor-train decomposition
- The convex geometry of linear inverse problems
- The Power of Convex Relaxation: Near-Optimal Matrix Completion
- Theta bodies for polynomial ideals
- Theta rank, levelness, and matroid minors
- Tight Oracle Inequalities for Low-Rank Matrix Recovery From a Minimal Number of Noisy Random Measurements
- Using Algebraic Geometry
Cited in
(15)- Completely positive tensor recovery with minimal nuclear value
- Recovery algorithms for high-dimensional rank one tensors
- On polynomial time methods for exact low-rank tensor completion
- Low rank tensor recovery via iterative hard thresholding
- Proximal gradient algorithm for nonconvex low tubal rank tensor recovery
- Conditions for the equivalence between the low-n-rank tensor recovery problem and its convex relaxation
- \(L^{\infty}\) estimation of tensor truncations
- Minimax Lower Bounds on Dictionary Learning for Tensor Data
- Tensor sparsification via a bound on the spectral norm of random tensors: Algorithm 1.
- N-Dimensional Tensor Completion for Nuclear Magnetic Resonance Relaxometry
- Symmetric tensor nuclear norms
- The Sup-norm Perturbation of HOSVD and Low Rank Tensor Denoising
- Low-rank tensor recovery using sequentially optimal modal projections in iterative hard thresholding (SeMPIHT)
- Algebraic compressed sensing
- Spectral methods for polynomial optimization
This page was built for publication: Tensor theta norms and low rank recovery
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2048814)
