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

DOI10.1016/J.ACHA.2018.12.003zbMATH Open1483.41010arXiv1711.11269OpenAlexW2890058448WikidataQ128626934 ScholiaQ128626934MaRDI QIDQ2175019FDOQ2175019

Mateusz Michalek, Yang Qi, Lek-Heng Lim

Publication date: 27 April 2020

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

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.

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)

Cites Work

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

Cited In (10)

• Best \(k\)-layer neural network approximations
• Guarantees for Existence of a Best Canonical Polyadic Approximation of a Noisy Low-Rank Tensor
• A note on nonclosed tensor formats
• On Best Low Rank Approximation of Positive Definite Tensors
• Title not available (Why is that?)
• Spurious Valleys, NP-Hardness, and Tractability of Sparse Matrix Factorization with Fixed Support
• An alternating shifted higher order power method based algorithm for rank-\(R\) Hermitian approximation and solving Hermitian CP-decomposition problems
• Uniform matrix product states from an algebraic geometer's point of view
• Title not available (Why is that?)
• 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)