Search

MiS Preprint Repository

We have decided to discontinue the publication of preprints on our preprint server as of 1 March 2024. The publication culture within mathematics has changed so much due to the rise of repositories such as ArXiV (www.arxiv.org) that we are encouraging all institute members to make their preprints available there. An institute's repository in its previous form is, therefore, unnecessary. The preprints published to date will remain available here, but we will not add any new preprints here.

MiS Preprint
79/2017

Complex tensors almost always have best low-rank approximations

Yang Qi, Mateusz Michałek and Lek-Heng Lim

Abstract

Low-rank tensor approximations are plagued by a well-known problem --- a tensor may fail to have a best rank-$r$ approximation. Over $\mathbb{R}$, it is known that such failures can occur with positive probability, sometimes with certainty: in $\mathbb{R}^{2 \times 2 \times 2}$, every tensor of rank $3$ fails to have a best rank-$2$ approximation. We will show that while such failures still occur over $\mathbb{C}$, they happen with zero probability. In fact we establish a more general result with useful implications on recent scientific and engineering applications that rely on sparse and/or low-rank approximations: Let $V$ be a complex vector space with a Hermitian inner product, and $X$ be a closed irreducible complex analytic variety in $V$. Given any complex analytic subvariety $Z \subseteq X$ with $\dim Z < \dim X$, we prove that a general $p \in V$ has a unique best $X$-approximation $\pi_X (p)$ that does not lie in $Z$. In particular, it implies that over $\mathbb{C}$, any tensor almost always has a unique best rank-$r$ approximation when $r$ is less than the generic rank. Our result covers many other notions of tensor rank: symmetric rank, alternating rank, Chow rank, Segre--Veronese rank, Segre--Grassmann rank, Segre--Chow rank, Veronese--Grassmann rank, Veronese--Chow rank, Segre--Veronese--Grassmann rank, Segre--Veronese--Chow rank, and more --- in all cases, a unique best rank-$r$ approximation almost always exist. It applies also to block-terms approximations of tensors: for any $r$, a general tensor has a unique best $r$-block-terms approximations. When applied to sparse-plus-low-rank approximations, we obtain that for any given $r$ and $k$, a general matrix has a unique best approximation by a sum of a rank-$r$ matrix and a $k$-sparse matrix 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.

Received:
Dec 6, 2017
Published:
Jan 5, 2018
MSC Codes:
15A69, 41A50, 41A52, 41A65, 97N50, 51M35

Related publications

inJournal
2020 Repository Open Access
Yang Qi, Mateusz Michałek and Lek-Heng Lim

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

In: Applied and computational harmonic analysis, 49 (2020) 1, pp. 180-207