Back to Search
Start Over
A Practical Randomized CP Tensor Decomposition
- Source :
- SIAM Journal on Matrix Analysis and Applications, Vol. 39, No. 2, pp. 876-901, 2018
- Publication Year :
- 2017
-
Abstract
- The CANDECOMP/PARAFAC (CP) decomposition is a leading method for the analysis of multiway data. The standard alternating least squares algorithm for the CP decomposition (CP-ALS) involves a series of highly overdetermined linear least squares problems. We extend randomized least squares methods to tensors and show the workload of CP-ALS can be drastically reduced without a sacrifice in quality. We introduce techniques for efficiently preprocessing, sampling, and computing randomized least squares on a dense tensor of arbitrary order, as well as an efficient sampling-based technique for checking the stopping condition. We also show more generally that the Khatri-Rao product (used within the CP-ALS iteration) produces conditions favorable for direct sampling. In numerical results, we see improvements in speed, reductions in memory requirements, and robustness with respect to initialization.
- Subjects :
- Computer Science - Numerical Analysis
Subjects
Details
- Database :
- arXiv
- Journal :
- SIAM Journal on Matrix Analysis and Applications, Vol. 39, No. 2, pp. 876-901, 2018
- Publication Type :
- Report
- Accession number :
- edsarx.1701.06600
- Document Type :
- Working Paper
- Full Text :
- https://doi.org/10.1137/17M1112303