Complex best r-term approximations almost always exist in finite dimensions

DOI10.1016/J.ACHA.2018.12.003MaRDI QIDQ2175019zbMATH OpenOpenAlexWikidataFDO

Authors Yang Qi, Mateusz Michalek, Lek-Heng Lim

Publication date 27 April 2020

Published in Applied and Computational Harmonic Analysis (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1711.11269

zbMATH Keywords

nonlinear approximationtensor ranktensor completiontensor networksbest rank-\(r\) approximationsparse-plus-low-rank approximation

Mathematics Subject Classification ID

Multilinear algebra, tensor calculus (15A69) Approximation in the complex plane (30E10) Uniqueness of best approximation (41A52) Approximation by arbitrary nonlinear expressions; widths and entropy (41A46)

Abstract: We show that in finite-dimensional nonlinear approximations, the best $r$-term approximant of a function $f$ almost always exists over $mathbbC$ but that the same is not true over $mathbbR$, i.e., the infimum $in{f}_{f_1,dots,f_{r}inY}lVertf-f_1-dots-f_{r}Vert$ is almost always attainable by complex-valued functions $f_1,dots,f_r$ in $Y$, a set of functions that have some desired structures. Our result extends to functions that possess special properties like symmetry or skew-symmetry under permutations of arguments. For the case where $Y$ is the set of separable functions, the problem becomes that of best rank-$r$ tensor approximations. We show that over $mathbbC$, any tensor almost always has a unique best rank-$r$ approximation. This extends to other notions of tensor ranks such as symmetric rank and alternating rank, to best $r$-block-terms approximations, and to best approximations by tensor networks. When applied to sparse-plus-low-rank approximations, we obtain that for any given $r$ and $k$, a general tensor has a unique best approximation by a sum of a rank-$r$ tensor and a $k$-sparse tensor with a fixed sparsity pattern; this arises in, for example, estimation of covariance matrices of a Gaussian hidden variable model with $k$ observed variables conditionally independent given $r$ hidden variables. The existential (but not the uniqueness) part of our result also applies to best approximations by a sum of a rank-$r$ tensor and a $k$-sparse tensor with no fixed sparsity pattern, as well as to tensor completion problems.

Recommendations

• On best rank-\(2\) and rank-\((2,2,2)\) approximations of order-\(3\) tensors
• Guarantees for existence of a best canonical polyadic approximation of a noisy low-rank tensor
• The number of singular vector tuples and uniqueness of best rank-one approximation of tensors
• Tensor Rank and the Ill-Posedness of the Best Low-Rank Approximation Problem
• Subtracting a best rank-1 approximation may increase tensor rank

Cites work

• scientific article; zbMATH DE number 5968745 (Why is no real title available?)
• scientific article; zbMATH DE number 52497 (Why is no real title available?)
• scientific article; zbMATH DE number 192849 (Why is no real title available?)
• scientific article; zbMATH DE number 575960 (Why is no real title available?)
• scientific article; zbMATH DE number 2079345 (Why is no real title available?)
• scientific article; zbMATH DE number 790015 (Why is no real title available?)
• A practical introduction to tensor networks: Matrix product states and projected entangled pair states
• A problem on completeness of exponentials
• Algebraic factor analysis: tetrads, pentads and beyond
• Applied multivariate statistical analysis.
• Approximation by superpositions of a sigmoidal function
• Compressed sensing
• Compressed sensing and best \(k\)-term approximation
• Compressive sampling
• Computing images of polynomial maps
• Decompositions of a Higher-Order Tensor in Block Terms—Part II: Definitions and Uniqueness
• Greedy approximation
• Grothendieck constant is norm of Strassen matrix multiplication tensor
• Lectures on algebraic statistics
• Matrix product state representations
• Neighborhoods of Algebraic Sets
• Nuclear norm of higher-order tensors
• On approximation of functions by exponential sums
• On the geometry of tensor network states
• On the minimal ranks of matrix pencils and the existence of a best approximate block-term tensor decomposition
• Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ ¹ minimization
• Rank-Sparsity Incoherence for Matrix Decomposition
• Recovering Low-Rank Matrices From Few Coefficients in Any Basis
• Robust principal component analysis?
• Semianalytic and subanalytic sets
• Some approximation problems in semi-algebraic geometry
• Sparse representations in unions of bases
• Symmetric Tensors and Symmetric Tensor Rank
• Tensor Rank and the Ill-Posedness of the Best Low-Rank Approximation Problem
• Tensor spaces and numerical tensor calculus
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• The density-matrix renormalization group in the age of matrix product states

Cited in

(10)

• Best \(k\)-layer neural network approximations
• A note on nonclosed tensor formats
• On Best Low Rank Approximation of Positive Definite Tensors
• Guarantees for existence of a best canonical polyadic approximation of a noisy low-rank tensor
• scientific article; zbMATH DE number 4107168 (Why is no real title available?)
• Spurious Valleys, NP-Hardness, and Tractability of Sparse Matrix Factorization with Fixed Support
• Uniform matrix product states from an algebraic geometer's point of view
• An alternating shifted higher order power method based algorithm for rank-\(R\) Hermitian approximation and solving Hermitian CP-decomposition problems
• scientific article; zbMATH DE number 6474941 (Why is no real title available?)
• Almost all subgeneric third-order Chow decompositions are identifiable

This page was built for publication: Complex best \(r\)-term approximations almost always exist in finite dimensions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2175019)