The DOI matches its Crossref record; 44 of the 44 references it cites were found in a registry or an index.
Tensor Rank and the Ill-Posedness of the Best Low-Rank Approximation Problem
Open accessAbstract
There has been continued interest in seeking a theorem describing optimal low-rank approximations to tensors of order 3 or higher that parallels the Eckart–Young theorem for matrices. In this paper, we argue that the naive approach to this problem is doomed to failure because, unlike matrices, tensors of order 3 or higher can fail to have best rank-r approximations. The phenomenon is much more widespread than one might suspect: examples of this failure can be constructed over a wide range of dimensions, orders, and ranks, regardless of the choice of norm (or even Brègman divergence). Moreover, we show that in many instances these counterexamples have positive volume: they cannot be regarded as isolated phenomena. In one extreme case, we exhibit a tensor space in which no rank-3 tensor has an optimal rank-2 approximation. The notable exceptions to this misbehavior are rank-1 tensors and order-2 tensors (i.e., matrices). In a more positive spirit, we propose a natural way of overcoming the ill-posedness of the low-rank approximation problem, by using weak solutions when true solutions do not exist. For this to work, it is necessary to characterize the set of weak solutions, and we do this in the case of rank 2, order 3 (in arbitrary dimensions). In our work we emphasize the importance of closely studying concrete low-dimensional examples as a first step toward more general results. To this end, we present a detailed analysis of equivalence classes of $2 \times 2 \times 2$ tensors, and we develop methods for extending results upward to higher orders and dimensions. Finally, we link our work to existing studies of tensors from an algebraic geometric point of view. The rank of a tensor can in theory be given a semialgebraic description; in other words, it can be determined by a system of polynomial inequalities. We study some of these polynomials in cases of interest to us; in particular, we make extensive use of the hyperdeterminant $\Delta$ on $\mathbb{R}^{2\times 2 \times 2}$.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Partial Differential Equations
(1988) · Lecture Notes in Mathematics · doi:10.1007/bfb0082920 · Cited by 23,383
Gantmacher, F. R. (1984) · UCLA - Biblioteca de Ciencias y Tecnologia Felix Morales Bueno · Cited by 8,520
Golub, G. H., & Loan, C. F. V. (1996) · Johns Hopkins University Press eBooks · Cited by 6,027
A Multilinear Singular Value Decomposition
De Lathauwer, L., De Moor, B., & Vandewalle, J. (2000) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/s0895479896305696 · Cited by 4,106
The Art of Computer Programming. Volume 2: Seminumerical Algorithms.
Taussky, O., & Knuth, D. E. (1970) · The American Mathematical Monthly · doi:10.2307/2317055 · Cited by 3,822
The Approximation of One Matrix by Another of Lower Rank
Eckart, C., & Young, G. (1936) · Psychometrika · doi:10.1007/bf02288367 · Cited by 3,800
Introductory functional analysis with applications
Kreyszig, E. (1978) · Cited by 2,889
Bregman, L. M. (1967) · USSR Computational Mathematics and Mathematical Physics · doi:10.1016/0041-5553(67)90040-7 · Cited by 2,618
Harshman, R. A. (1970) · Cited by 2,255
A Decision Method for Elementary Algebra and Geometry
Tarski, A. (1998) · Texts and Monographs in Symbolic Computation · doi:10.1007/978-3-7091-9459-1_3 · Cited by 1,643
Cited by
Tensor Decompositions and Applications
Kolda, T. G., & Bader, B. W. (2009) · SIAM Review · doi:10.1137/07070111x · Cited by 10,301
Oseledets, I. V. (2011) · SIAM Journal on Scientific Computing · doi:10.1137/090752286 · Cited by 2,636
Cichocki, A., Mandic, D., De Lathauwer, L., Zhou, G., Zhao, Q., Caiafa, C., & PHAN, H. A. (2015) · IEEE Signal Processing Magazine · doi:10.1109/msp.2013.2297439 · Cited by 1,384
Factorization strategies for third-order tensors
Kilmer, M. E., & Martin, C. D. (2011) · Linear Algebra and its Applications · doi:10.1016/j.laa.2010.09.020 · Cited by 1,349
Most Tensor Problems Are NP-Hard
Hillar, C. J., & Lim, L.-H. (2013) · Journal of the ACM · doi:10.1145/2512329 · Cited by 1,099
Self-citationThe Convex Geometry of Linear Inverse Problems
Chandrasekaran, V., Recht, B., Parrilo, P. A., & Willsky, A. S. (2012) · Foundations of Computational Mathematics · doi:10.1007/s10208-012-9135-7 · Cited by 886
Bayesian CP Factorization of Incomplete Tensors with Automatic Rank Determination
Zhao, Q., Zhang, L., & Cichocki, A. (2015) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2015.2392756 · Cited by 587
A literature survey of low‐rank tensor approximation techniques
Grasedyck, L., Kressner, D., & Tobler, C. (2013) · GAMM-Mitteilungen · doi:10.1002/gamm.201310004 · Cited by 577
Symmetric Tensors and Symmetric Tensor Rank
Comon, P., Golub, G., Lim, L.-H., & Mourrain, B. (2008) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/060661569 · Cited by 544
Self-citationHierarchical Singular Value Decomposition of Tensors
Grasedyck, L. (2010) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/090764189 · Cited by 508
Breaking the Curse of Dimensionality, Or How to Use SVD in Many Dimensions
Oseledets, I. V., & Tyrtyshnikov, E. E. (2009) · SIAM Journal on Scientific Computing · doi:10.1137/090748330 · Cited by 459
Tensor decompositions, alternating least squares and other tales
Comon, P., Luciani, X., & de Almeida, A. L. F. (2009) · Journal of Chemometrics · doi:10.1002/cem.1236 · Cited by 457
Cichocki, A., Lee, N., Oseledets, I., Phan, A.-H., Zhao, Q., & Mandic, D. P. (2016) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000059 · Cited by 456
Coarse-graining renormalization by higher-order singular value decomposition
Xie, Z. Y., Chen, J., Qin, M. P., Zhu, J. W., Yang, L. P., & Xiang, T. (2012) · Physical Review B · doi:10.1103/physrevb.86.045139 · Cited by 394
Tensors : A brief introduction
Comon, P. (2014) · IEEE Signal Processing Magazine · doi:10.1109/msp.2014.2298533 · Cited by 347
Convolutional neural networks with low-rank regularization
Tai, C., Xiao, T., Zhang, Y., Wang, X., & Weinan, E. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1511.06067 · Cited by 341
The Alternating Linear Scheme for Tensor Optimization in the Tensor Train Format
Holtz, S., Rohwedder, T., & Schneider, R. (2012) · SIAM Journal on Scientific Computing · doi:10.1137/100818893 · Cited by 337
Neural Network Potential Energy Surfaces for Small Molecules and Reactions
Manzhos, S., & Carrington, T. (2021) · Chemical Reviews · doi:10.1021/acs.chemrev.0c00665 · Cited by 329
Speeding-up Convolutional Neural Networks Using Fine-tuned CP-Decomposition
Lebedev, V., Ganin, Y., Rakhuba, M., Oseledets, I. V., & Lempitsky, V. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1412.6553 · Cited by 283
Smooth PARAFAC Decomposition for Tensor Completion
Yokota, T., Zhao, Q., & Cichocki, A. (2016) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2016.2586759 · Cited by 279
O(dlog N)-Quantics Approximation of N-d Tensors in High-Dimensional Numerical Modeling
Khoromskij, B. N. (2011) · Constructive Approximation · doi:10.1007/s00365-011-9131-1 · Cited by 279
A New Truncation Strategy for the Higher-Order Singular Value Decomposition
Vannieuwenhoven, N., Vandebril, R., & Meerbergen, K. (2012) · SIAM Journal on Scientific Computing · doi:10.1137/110836067 · Cited by 277
On Tensors, Sparsity, and Nonnegative Factorizations
Chi, E. C., & Kolda, T. G. (2012) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/110859063 · Cited by 274
Sorber, L., Van Barel, M., & De Lathauwer, L. (2013) · SIAM Journal on Optimization · doi:10.1137/120868323 · Cited by 273
Denoising of Hyperspectral Images Using the PARAFAC Model and Statistical Performance Analysis
Liu, X., Bourennane, S., & Fossati, C. (2012) · IEEE Transactions on Geoscience and Remote Sensing · doi:10.1109/tgrs.2012.2187063 · Cited by 269
Approximation of $2^d\times2^d$ Matrices Using Tensor Decomposition
Oseledets, I. V. (2010) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/090757861 · Cited by 174
Learning Representations from Imperfect Time Series Data via Tensor Rank Regularization
Liang, P. P., Liu, Z., Tsai, Y.-H. H., Zhao, Q., Salakhutdinov, R., & Morency, L.-P. (2019) · Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics · doi:10.18653/v1/p19-1152 · Cited by 95
Quantifying entanglement from the geometric perspective
(2025) · doi:10.1209/0295-5075/adffb5 · Cited by 4
Metadata
- Authors
- de Silva, V., & Lim, L.-H.
- Venue
- SIAM Journal on Matrix Analysis and Applications
- Published
- 2008-01
- Volume
- 30
- Issue
- 3
- Pages
- 1084-1127
- ISSN
- 0895-4798 (ISSN-L)
- 1095-7162
- OpenAlex
- W2132267493
- Cited by
- 927
- References
- 44
- FWCI
- 16.28
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.