Scalable tensor factorizations for incomplete data
Open accessThe DOI matches its Crossref record; 32 of the 32 references it cites were found in a registry or an index.
Abstract
The problem of incomplete data – i.e., data with missing or unknown values – in multi-way arrays is ubiquitous in biomedical signal processing, network traffic analysis, bibliometrics, social network analysis, chemometrics, computer vision, communication networks, etc. We consider the problem of how to factorize data sets with missing values with the goal of capturing the underlying latent structure of the data and possibly reconstructing missing values (i.e., tensor completion). We focus on one of the most well-known tensor factorizations that captures multi-linear structure, CANDECOMP/PARAFAC (CP). In the presence of missing data, CP can be formulated as a weighted least squares problem that models only the known entries. We develop an algorithm called CP-WOPT (CP Weighted OPTimization) that uses a first-order optimization approach to solve the weighted least squares problem. Based on extensive numerical experiments, our algorithm is shown to successfully factorize tensors with noise and up to 99% missing data. A unique aspect of our approach is that it scales to sparse large-scale data, e.g., 1000 × 1000 × 1000 with five million known entries (0.5% dense). We further demonstrate the usefulness of CP-WOPT on two real-world applications: a novel EEG (electroencephalogram) application where missing data is frequently encountered due to disconnections of electrodes and the problem of modeling computer network traffic where data may be absent due to the expense of the data collection process.
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
Maximum Likelihood from Incomplete Data Via the EM Algorithm
Dempster, A. P., Laird, N. M., & Rubin, D. B. (1977) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1977.tb01600.x · Cited by 50,444
Delorme, A., & Makeig, S. (2004) · Journal of Neuroscience Methods · doi:10.1016/j.jneumeth.2003.10.009 · Cited by 24,371 · cited 1×
“The 3-D head images were drawn using EEGLab [35].”
Method(2021) · A First Course in Statistical Programming with R · doi:10.1017/9781108993456.011 · Cited by 13,724
Tensor Decompositions and Applications
Kolda, T. G., & Bader, B. W. (2009) · SIAM Review · doi:10.1137/07070111x · Cited by 10,301
Self-citation(1999) · Springer Series in Operations Research and Financial Engineering · doi:10.1007/b98874 · Cited by 9,482
Carroll, J. D., & Chang, J.-J. (1970) · Psychometrika · doi:10.1007/bf02310791 · Cited by 4,678
Some Mathematical Notes on Three-Mode Factor Analysis
Tucker, L. R. (1966) · Psychometrika · doi:10.1007/bf02289464 · Cited by 3,492
Harshman, R. A. (1970) · Cited by 2,255
The Power of Convex Relaxation: Near-Optimal Matrix Completion
Candes, E. J., & Tao, T. (2010) · IEEE Transactions on Information Theory · doi:10.1109/tit.2010.2044061 · Cited by 2,060
Candes, E. J., & Plan, Y. (2010) · Proceedings of the IEEE · doi:10.1109/jproc.2009.2035722 · Cited by 1,709
Kruskal, J. B. (1977) · Linear Algebra and its Applications · doi:10.1016/0024-3795(77)90069-6 · Cited by 1,619
Andersson, C. A., & Bro, R. (2000) · Chemometrics and Intelligent Laboratory Systems · doi:10.1016/s0169-7439(00)00071-x · Cited by 1,229
Weighted low-rank approximations
Srebro, N., & Jaakkola, T. (2003) · International Conference on Machine Learning · Cited by 715
Line search algorithms with guaranteed sufficient decrease
Moré, J. J., & Thuente, D. J. (1994) · ACM Transactions on Mathematical Software · doi:10.1145/192115.192132 · Cited by 528
Unsupervised Multiway Data Analysis: A Literature Survey
Acar, E., & Yener, B. (2009) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2008.112 · Cited by 434
Self-citationDecomposing EEG data into space–time–frequency components using Parallel Factor Analysis
Miwakeichi, F., Martı́nez-Montes, E., Valdés-Sosa, P. A., Nishiyama, N., Mizuhara, H., & Yamaguchi, Y. (2004) · NeuroImage · doi:10.1016/j.neuroimage.2004.03.039 · Cited by 374
A weighted non-negative least squares algorithm for three-way ‘PARAFAC’ factor analysis
Paatero, P. (1997) · Chemometrics and Intelligent Laboratory Systems · doi:10.1016/s0169-7439(97)00031-2 · Cited by 340
Damped Newton Algorithms for Matrix Factorization with Missing Data
Buchanan, A. M., & Fitzgibbon, A. W. (2005) · 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05) · doi:10.1109/cvpr.2005.118 · Cited by 299
Lower Rank Approximation of Matrices by Least Squares With Any Choice of Weights
Gabriel, K. R., & Zamir, S. (1979) · Technometrics · doi:10.1080/00401706.1979.10489819 · Cited by 295
A scalable optimization approach for fitting canonical tensor decompositions
Acar, E., Dunlavy, D. M., & Kolda, T. G. (2011) · Journal of Chemometrics · doi:10.1002/cem.1335 · Cited by 290
Self-citationMultiway analysis of epilepsy tensors
Acar, E., Aykut-Bingol, C., Bingol, H., Bro, R., & Yener, B. (2007) · Bioinformatics · doi:10.1093/bioinformatics/btm210 · Cited by 267
Self-citationHigher-Order Web Link Analysis Using Multilinear Algebra
Kolda, T. G., Bader, B. W., & Kenny, J. P. (2006) · Fifth IEEE International Conference on Data Mining (ICDM'05) · doi:10.1109/icdm.2005.77 · Cited by 252
Self-citationReview on Multiway Analysis in Chemistry—2000–2005
Bro, R. (2006) · Critical Reviews in Analytical Chemistry · doi:10.1080/10408340600969965 · Cited by 224
Walczak, B., & Massart, D. L. (2001) · Chemometrics and Intelligent Laboratory Systems · doi:10.1016/s0169-7439(01)00131-9 · Cited by 202
Weighted Least Squares Fitting Using Ordinary Least Squares Algorithms
Kiers, H. A. L. (1997) · Psychometrika · doi:10.1007/bf02295279 · Cited by 199
Optimizing resolution in multidimensional NMR by three-way decomposition
Orekhov, V. Y., Ibraghimov, I., & Billeter, M. (2003) · Journal of Biomolecular NMR · doi:10.1023/a:1024944720653 · Cited by 184
Dealing with missing data: Part II
Walczak, B., & Massart, D. L. (2001) · Chemometrics and Intelligent Laboratory Systems · doi:10.1016/s0169-7439(01)00132-0 · Cited by 173
Mørup, M., Hansen, L. K., & Arnfred, S. (2007) · Journal of Neuroscience Methods · doi:10.1016/j.jneumeth.2006.11.008 · Cited by 150
Self-citationScalable Tensor Factorizations with Missing Data
Acar, E., Dunlavy, D., Kolda, T. G., & Mørup, M. (2010) · SIAM International Conference on Data Mining · doi:10.1137/1.9781611972801.61 · Cited by 143
Self-citationPoblano v1.0 : a Matlab toolbox for gradient-based optimization.
Dunlavy, D., Acar, E., & Kolda, T. G. (2010) · doi:10.2172/989350 · Cited by 86
Self-citationProceedings of the Seventh SIAM International Conference on Data Mining
Apte, C., Liu, B., & Parthasarathy, S. (2007) · Society for Industrial and Applied Mathematics eBooks · Cited by 43
Fitting Arma Time Series by Structural Equation Models
van Buuren, S. (1997) · Psychometrika · doi:10.1007/bf02295276 · Cited by 35
Cited by
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
missMDA: A Package for Handling Missing Values in Multivariate Data Analysis
Josse, J., & Husson, F. (2016) · Journal of Statistical Software · doi:10.18637/jss.v070.i01 · Cited by 1,344
Multimodal Data Fusion: An Overview of Methods, Challenges, and Prospects
Lahat, D., Adali, T., & Jutten, C. (2015) · Proceedings of the IEEE · doi:10.1109/jproc.2015.2460697 · Cited by 1,296
“It turns out that the same applies also in the case of missing values, see [16], [99], [160]–[162] and references therein.”
BackgroundBayesian 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 tensor-based method for missing traffic data completion
Tan, H., Feng, G., Feng, J., Wang, W., Zhang, Y.-J., & Li, F. (2013) · Transportation Research Part C: Emerging Technologies · doi:10.1016/j.trc.2012.12.007 · Cited by 427
Metadata
- Authors
- Acar, E., Dunlavy, D. M., Kolda, T. G., & Mørup, M.
- Venue
- Chemometrics and Intelligent Laboratory Systems
- Publisher
- Elsevier BV
- Published
- 2011-03
- Volume
- 106
- Issue
- 1
- Pages
- 41-56
- ISSN
- 0169-7439 (ISSN-L)
- OpenAlex
- W1814521481
- Cited by
- 602
- References
- 32
- FWCI
- 8.27
- 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.