MiS Preprint Repository

Delve into the future of research at MiS with our preprint repository. Our scientists are making groundbreaking discoveries and sharing their latest findings before they are published. Explore repository to stay up-to-date on the newest developments and breakthroughs.

MiS Preprint

Complex tensors almost always have best low-rank approximations

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


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.

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

Related publications

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