PaperlayerView exact revision on arXiv

Source-linked AI summary

A Practical Randomized CP Tensor Decomposition

Casey Battaglino, Grey Ballard, Tamara G. Kolda

arXiv:1701.06600v2math.NA

TL;DR

CP-ALS repeatedly solves highly overdetermined least-squares problems, motivating a lower-cost randomized alternative. The paper develops sampled and mixing-based tensor least-squares methods, reports reduced overhead and improved robustness, and identifies input-dependent incoherence as a scope boundary.

  • Problem

    CP-ALS relies on repeated least-squares solves, but it was unclear whether sketching would help because its subproblems already have special structure.

  • Method

    The paper extends randomized least-squares methods to tensors through CPRAND sampling and CPRAND-MIX preprocessing, mixing, and sampling without explicitly forming full Khatri-Rao matrices.

  • Results

    The randomized algorithms significantly reduce CP-ALS memory and computational overhead and improve robustness, with CPRAND faster and less sensitive to initialization than CP-ALS.

  • Takeaways & Limitations

    Randomized least-squares methods can make dense-tensor CP-ALS substantially more efficient while retaining solution quality and improving robustness.

  • Takeaways & Limitations

    Guaranteed incoherence requires a preprocessing mixing step regardless of the input, while direct sampling benefits from favorable Khatri-Rao coherence conditions.

Abstract

from arXiv · show

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.

1. Introduction.

The paper applies randomized least-squares methods to CP-ALS, reducing computational and memory overhead while improving robustness. CPRAND methods converge quickly in the illustrated noisy synthetic example.

  • 1. Introduction.: Randomized algorithms significantly reduce CP-ALS memory and computational overhead while improving algorithmic robustness.The paper presents this as its first successful application of matrix sketching methods to CP decomposition.
  • 1. Introduction.: CPRAND uses randomized least-squares solves, while CPRAND-MIX adds efficient mixing to promote incoherence and improve robustness.Neither algorithm explicitly forms the full Khatri-Rao matrices used in the subproblems.
  • 1. Introduction.: CPRAND is faster and much less sensitive to initialization than CP-ALS across synthetic and real-world experiments.The authors also introduce a sampling-based stopping condition with Chernoff-Hoeffding accuracy guarantees.
  • 1. Introduction.: In the synthetic runtime comparison, CPRAND and CPRAND-MIX use random initialization and 100 sampled rows per least-squares solve, whereas CP-ALS uses HOSVD initialization.The tensors have rank 5, factor collinearity 0.9, and 1% noise; the 99% fit line is the expected noise-limited target.

2. Background and Definitions.

This section introduces tensors, CP structure, randomized least-squares sketching, leverage scores, coherence, and mixing-based sampling. These concepts motivate uniform sampling after transformations that distribute leverage across rows.

  • 2. Background and Definitions.: A tensor is treated as a multidimensional array with order N, and mode-n fibers become columns in the mode-n unfolding.The unfolding has dimensions determined by mode n and the product of the remaining mode sizes.
  • 2. Background and Definitions.: The CP decomposition approximates an order-N tensor as a sum of R rank-one components represented by factor matrices and optional component weights.Normalizing factor vectors and collecting scale into λ_r addresses scaling ambiguity in the representation.
  • 2. Background and Definitions.: CP matricization satisfies ˜X^(n) = A^(n)Z^(n)T, where Z^(n) is the Khatri-Rao product of all factor matrices except mode n.The Khatri-Rao product is the matching columnwise Kronecker product.
  • 2. Background and Definitions.: Sketching replaces an overdetermined least-squares problem with a smaller projected problem whose exact solution approximates the original with high probability.The projection reduces an n-by-d regression to S rows with S much smaller than n.
  • 2. Background and Definitions.: Uniform sampling is effective when leverage scores are spread across rows; mixing is used to promote this incoherence before sampling.The FJLT applies random sign flips, a fast mixing transform, and uniform row sampling, while the paper uses FFT mixing.
  • 2. Background and Definitions.: The CP-ALS coefficient matrix may become incoherent through its Khatri-Rao structure, but preprocessing is necessary to guarantee incoherence regardless of input.High coherence can make uniform sampling nearly rank-deficient and produce inaccurate solutions.

3. Algorithms.

The algorithms modify CP-ALS by solving sampled least-squares subproblems and computing sampled Khatri-Rao rows without forming full coefficient matrices. Initialization, Gram products, and tensor contractions determine the baseline costs these methods target.

  • 3.1. CP-ALS.: CP-ALS alternates over modes, fixing all factor matrices except A^(n) and solving a least-squares problem for the remaining factor.Its normal-equation formulation uses the Khatri-Rao coefficient matrix and Gram products.
  • 3.1. CP-ALS.: HOSVD initialization uses leading singular vectors of each mode-n unfolding, while random initialization is cheaper but less effective.Initialization can substantially affect algorithm performance.
  • 3.1. CP-ALS.: The dominant CP-ALS work includes MTTKRP and tensor–Khatri-Rao multiplication, with each outer iteration costing O(NR∏_m I_m) flops.The least-squares solve is cheaper than the main tensor contraction in the stated cost discussion.
  • 3.2. CPRAND.: CPRAND samples rows of the Khatri-Rao coefficient matrix and corresponding unfolded-tensor rows without explicitly forming the full product.Sampling uses uniform sampling with replacement, so rows may be selected more than once.
  • 3.2. CPRAND.: Figure 2 links sampled Khatri-Rao rows to sampled fibers of the original tensor.This correspondence enables sampling-based construction of the least-squares data.
  • 3.2. CPRAND.: A sampled Khatri-Rao row is computed as the Hadamard product of the corresponding rows from the factor matrices.Index tuples identify the factor rows associated with each sampled row.

S 7: end for 8: return ZS 9: end function

The paper reduces CP-ALS cost by solving sampled least-squares subproblems without explicitly forming large tensor matrices, while exploiting Khatri-Rao coherence and mixing when needed. It also introduces a sampled stopping criterion with theoretically controlled accuracy and reports computational trade-offs for CPRAND-MIX.

  • CPRAND: CPRAND samples rows of the Khatri-Rao coefficient matrix and tensor unfolding, then solves a reduced S × R least-squares problem to obtain each In × R factor matrix.The sampled coefficient matrix is formed without explicitly constructing the full Khatri-Rao matrix, and tensor fibers can be pulled directly without matricization.
  • Cost: The leading cost per inner update is 2SRIn operations under In > R and S > R, while sampling requires generating random multiindices and computing sampled Khatri-Rao rows.The overall outer-iteration cost scales with the number of samples rather than the full tensor dimensions.
  • Coherence: The Khatri-Rao product inherits incoherence from its factor matrices, and the coherence bound can yield a large reduction, although the bound is tight in specific examples.This property supports direct sampling because lower coherence makes uniform sampling more effective.
  • CPRAND-MIX: CPRAND-MIX applies mixing to promote incoherence, using upfront tensor preprocessing, mode-specific unmixing, and implicit sampling of the mixed Khatri-Rao product.The method avoids repeatedly mixing the full Khatri-Rao matrix because only one factor changes during each outer iteration.
  • Cost: Algorithm 4 increases the leading per-iteration cost by a factor of 2 compared with CPRAND because the real-arithmetic least-squares system has twice as many coefficient rows.Complex-valued operations individually cost a constant factor between 2 and 4, while the stated leading-order comparison is a factor of 2.
  • Stopping Criteria: The sampled stopping criterion estimates relative residual error from tensor-entry samples, with Chernoff-Hoeffding analysis requiring i.i.d. errors drawn from a finite distribution.For a 5% multiplicative error and 98% confidence, the supplied analysis gives γ = 0.1025 and requires P̂ ≥ 372μ².

4. Experiments.

Experiments show that randomized CP-ALS variants substantially reduce iteration, fit-check, and often total runtime while maintaining comparable or better solution quality and robustness. These benefits are demonstrated on synthetic tensors and a real hazardous-gas classification dataset, with initialization and iteration-count trade-offs.

  • Computational Time: Up to 500× lower per-iteration cost was observed for randomized methods on fifth-order tensors, compared with up to 50× for third-order tensors.The randomized cost scales as O(NRIS), versus O(NRIN) flops per CP-ALS iteration.
  • Computational Time: More than two orders of magnitude faster fit checks were observed on the largest tested tensors using 214 sampled entries.The largest relative error between exact and sampled fit was less than 10^-3.
  • Synthetic Data: Randomized methods achieved similar median fits, with a maximum difference of 0.006, while CP-ALS with random initialization had the highest fit variance.The reported fits use the true final fit even when approximate fits guide termination.
  • Synthetic Data: At 10% noise, CPRAND and CPRAND-MIX had median scores above 0.85 or 0.92, while CP-ALS medians were below 0.73 or 0.89 for the third- and fourth-order cases.At 1% noise, methods generally performed well, with medians above 0.97 or 0.99 depending on tensor order.
  • Synthetic Data: Randomized methods required more iterations than CP-ALS with HOSVD initialization because they generally made less progress per iteration, and every method except CP-ALS(H) reached 200 iterations at least once.This trade-off accompanies the lower per-iteration cost.
  • Hazardous Gases: On the hazardous-gas tensor, CPRAND was nearly 4× faster than CP-ALS with random initialization and 10× faster than CP-ALS with HOSVD initialization, with comparable classification error.Median classification error was 0.61% for CPRAND versus 0.67% for both ALS variants.

5. Related Work.

The paper situates its dense-tensor CP approach among randomized least-squares, leverage-score, sketching, compression, and related CP methods, emphasizing its focus on the least-squares subproblem.

  • 5. Related Work.: Leverage-score sampling has been applied to sparse CP decomposition by estimating unfolded-tensor leverage scores from factor-matrix leverage scores.
  • 5. Related Work.: Sketching methods have been developed for orthogonal tensors, including sublinear-time computation under certain conditions.
  • 5. Related Work.: Other related approaches compress tensors using lossy Tucker representations or direct sampling before performing decomposition.
  • 5. Related Work.: The approach focuses on randomized least squares within CP-ALS rather than compressing the tensor before decomposition.This focus leverages existing randomized least-squares theory and methodology.

6. Conclusion.

The conclusion presents CPRAND and CPRAND-MIX as randomized CP-ALS methods that reduce computational expense while retaining equivalent-quality decompositions, but identifies unresolved sampling, optimality, and scalability boundaries.

  • 6. Conclusion.: CPRAND avoids explicitly forming the Khatri-Rao matrix, reducing the primary expense of the CP-ALS least-squares solve.The standard solve requires forming the Khatri-Rao matrix and multiplying by the matricized tensor.
  • 6. Conclusion.: CPRAND-MIX uses an FJLT-style preprocessing step to promote incoherence, with FFT-based mixing adding initialization cost and doubling memory for real-valued problems.The inverse transform is applied only to the small sampled matrix during each solve.
  • 6. Conclusion.: Subsampling tensor entries provides a lower-cost stopping condition that approximates model-fit error when errors are i.i.d. and drawn from a finite distribution.
  • 6. Conclusion.: The randomized methods are faster than CP-ALS for equivalent-quality decompositions and less sensitive to initialization on synthetic and real tensors up to 13 GB.The authors conjecture that randomization may prevent local minima caused by overfitting noise.
  • 6. Conclusion.: The randomized stopping process lacks a rigorous sample-size rule; in practice, the authors find that 10–100 times R samples is sufficient.The paper identifies further theoretical work as necessary to justify this choice.
  • 6. Conclusion.: Because CP fitting is non-convex, neither CP-ALS nor its randomized variants guarantee global optimality or monotonic objective improvement.
  • 6. Conclusion.: Future work includes reducing random-fiber extraction costs, proving the mixing operator is an FJLT, extending methods to sparse tensors, and studying distributed or out-of-core applications.The authors suspect non-uniform sampling without mixing may be more effective for sparse data.
Loading 1701.06600v2…