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
On the Best Rank-1 and Rank-(R1 ,R2 ,. . .,RN) Approximation of Higher-Order Tensors
De Lathauwer, L., De Moor, B., & Vandewalle, J. (2000) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/s0895479898346995 · Cited by 1,567
The Expression of a Tensor or a Polyadic as a Sum of Products
Hitchcock, F. L. (1927) · Journal of Mathematics and Physics · doi:10.1002/sapm192761164 · Cited by 1,345
Rounding errors in algebraic processes
(1964) · Journal of the Franklin Institute · doi:10.1016/0016-0032(64)90390-4 · Cited by 1,315
Multi‐Way Analysis with Applications in the Chemical Sciences
Smilde, A., Bro, R., & Geladi, P. (2004) · Wiley eBooks · doi:10.1002/0470012110 · Cited by 1,176
Bürgisser, P., Clausen, M., & Shokrollahi, M. A. (1997) · Grundlehren der mathematischen Wissenschaften · doi:10.1007/978-3-662-03338-8 · Cited by 1,026
Algebraic geometry: a first course
(1993) · Choice Reviews Online · doi:10.5860/choice.30-5053a · Cited by 998
Tensor Norms and Operator Ideals
(1993) · North-Holland Mathematics Studies · doi:10.1016/s0304-0208(08)x7019-7 · Cited by 839
Håstad, J. (1990) · Journal of Algorithms · doi:10.1016/0196-6774(90)90014-6 · Cited by 584
Olver, P. J. (1999) · Cambridge University Press eBooks · doi:10.1017/cbo9780511623660 · Cited by 554
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-citationA New Decision Method for Elementary Algebra
Seidenberg, A. (1954) · Annals of Mathematics · doi:10.2307/1969640 · Cited by 541
Rank-One Approximation to High Order Tensors
Zhang, T., & Golub, G. H. (2001) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/s0895479899352045 · Cited by 430
On the Best Rank-1 Approximation of Higher-Order Supersymmetric Tensors
Kofidis, E., & Regalia, P. A. (2002) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/s0895479801387413 · Cited by 387
Finite dimensional multilinear algebra
Marcus, M. D. (1973) · CERN Document Server (European Organization for Nuclear Research) · Cited by 377
Orthogonal Tensor Decompositions
Kolda, T. G. (2001) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/s0895479800368354 · Cited by 376
Multiple Invariants and Generalized Rank of a P‐Way Matrix or Tensor
Hitchcock, F. L. (1928) · Journal of Mathematics and Physics · doi:10.1002/sapm19287139 · Cited by 338
On condition numbers and the distance to the nearest ill-posed problem
Demmel, J. W. (1987) · Numerische Mathematik · doi:10.1007/bf01400115 · Cited by 302
Ill-Conditioned Eigensystems and the Computation of the Jordan Canonical Form
Golub, G. H., & Wilkinson, J. H. (1976) · SIAM Review · doi:10.1137/1018113 · Cited by 278
Rank, decomposition, and uniqueness for 3-way and n -way arrays
Kruskal, J. B. (1989) · Medical Entomology and Zoology · Cited by 253
Multilinear image analysis for facial recognition
Vasilescu, M. A. O., & Terzopoulos, D. (2003) · Object recognition supported by user interaction for service robots · doi:10.1109/icpr.2002.1048350 · Cited by 229
The probability that a numerical analysis problem is difficult
Demmel, J. W. (1988) · Mathematics of Computation · doi:10.1090/s0025-5718-1988-0929546-7 · Cited by 221
O(n2.7799) complexity for n × n approximate matrix multiplication
Bini, D., Capovani, M., Romani, F., & Lotti, G. (1979) · Information Processing Letters · doi:10.1016/0020-0190(79)90113-3 · Cited by 207
Matrix Nearness Problems with Bregman Divergences
Dhillon, I. S., & Tropp, J. A. (2008) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/060649021 · Cited by 189
TensorTextures: multilinear image-based rendering
Vasilescu, M. A. O., & Terzopoulos, D. (2004) · ACM Transactions on Graphics · doi:10.1145/1015706.1015725 · Cited by 167
Human motion signatures: analysis, synthesis, recognition
Vasilescu, M. A. O. (2003) · doi:10.1109/icpr.2002.1047975 · Cited by 134
On the Ideals of Secant Varieties of Segre Varieties
Landsberg, J. M., & Manivel, L. (2004) · Foundations of Computational Mathematics · doi:10.1007/s10208-003-0115-9 · Cited by 123
The border rank of the multiplication of 2×2 matrices is seven
Landsberg, J. M. (2005) · Journal of the American Mathematical Society · doi:10.1090/s0894-0347-05-00506-0 · Cited by 76
Gelfand, I. M., Kapranov, M. M., & Zelevinsky, A. V. (1992) · Advances in Mathematics · doi:10.1016/0001-8708(92)90056-q · Cited by 61
The hyperdeterminant and triangulations of the 4-cube
Huggins, P. M., Sturmfels, B., Yu, J., & Yuster, D. S. (2008) · Mathematics of Computation · doi:10.1090/s0025-5718-08-02073-5 · Cited by 58
Stegeman, A. (2008) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/050644677 · Cited by 53
Border rank of a p×q×2 tensor and the optimal approximation of a pair of bilinear forms
Bini, D. A. (1980) · Lecture notes in computer science · doi:10.1007/3-540-10003-2_63 · Cited by 28
Bounds on the ranks of some 3-tensors
Atkinson, M. D., & Lloyd, S. (1980) · Linear Algebra and its Applications · doi:10.1016/0024-3795(80)90202-5 · Cited by 24
Ranks of tensors and change of base field
Bergman, G. M. (1969) · Journal of Algebra · doi:10.1016/0021-8693(69)90094-5 · Cited by 22
Genericity And Rank Deficiency Of High Order Symmetric Tensors
Comon, P., Mourrain, B., Lim, L., & Golub, G. H. (2006) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp.2006.1660606 · Cited by 10
Self-citation
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-citation
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.