PaperlayerView exact revision on arXiv

Source-linked AI summary

Sampling-Based Decomposition Algorithms for Arbitrary Tensor Networks

Osman Asif Malik, Vivek Bharadwaj, Riley Murray

arXiv:2210.03828v1math.NAcs.LGcs.NA

TL;DR

Tensor decomposition by ALS inherits costs that grow exponentially with the number of tensor modes, while prior sampling-based methods address specific formats. This paper develops exact-leverage-score sampling for ALS across TN formats under mild assumptions and reports improved runtime over [18] for CP and tensor ring.

  • Problem

    ALS iterations involving all tensor entries inherit exponential dependence on the number of modes, while prior sampling-based ALS methods addressed specific tensor decompositions.

    Source: §1 · p. 1

  • Method

    The framework samples according to exact leverage scores and yields input-sublinear per-iteration ALS algorithms for TN decompositions satisfying mild assumptions.

    Source: §1 · p. 2

  • Results

    Complexity analyses and numerical experiments confirm improved runtime over [18] when the framework is used for CP and tensor ring decomposition.

    Source: §7 · p. 13

  • Takeaways & Limitations

    The framework generalizes sampling-based ALS beyond specific decomposition formats while retaining exact leverage-score sampling.

    Source: §7 · p. 13

    Efficiency relies on tractable TN contractions, and avoiding the Ω(R^3) pseudoinverse cost for general TN matrices remains an open direction.

    Source: §4.2 · p. 8, §7 · p. 13

Abstract

from arXiv · show

We show how to develop sampling-based alternating least squares (ALS) algorithms for decomposition of tensors into any tensor network (TN) format. Provided the TN format satisfies certain mild assumptions, resulting algorithms will have input sublinear per-iteration cost. Unlike most previous works on sampling-based ALS methods for tensor decomposition, the sampling in our framework is done according to the exact leverage score distribution of the design matrices in the ALS subproblems. We implement and test two tensor decomposition algorithms that use our sampling framework in a feature extraction experiment where we compare them against a number of other decomposition algorithms.

1 Introduction

Tensor decomposition methods face per-iteration costs that inherit the exponential size of an N-mode tensor. This work extends sampling-based ALS to arbitrary TN formats under mild assumptions, with exact leverage-score sampling and input-sublinear per-iteration cost.

1 Introduction

  • A tensor with N modes of dimension I contains I^N entries, so ALS iterations that use all entries inherit exponential dependence on N.Each ALS iteration solves least-squares problems with tensor entries as dependent variables.Source: §1 · p. 1
  • Earlier sampling-based ALS work sought per-iteration cost below the number of tensor entries by sampling least-squares subproblems using leverage scores or approximations.The cited approaches exploit special structure in the design matrices.Source: §1 · pp. 1–2
  • The framework extends beyond methods for specific decompositions to TN formats that include CP, Tucker, tensor train, and tensor ring.Earlier sampling-based ALS methods discussed here target CP, Tucker, or tensor ring.Source: §1 · p. 2
  • Exact leverage-score sampling of rows in tall-and-skinny TN matrices underpins the proposed sampling framework.The paper establishes how to sample according to the exact leverage-score distribution.Source: §1 · p. 2
  • Sampling-based ALS for qualifying TN decompositions achieves input-sublinear per-iteration cost.The framework applies to all TN decompositions satisfying certain mild assumptions.Source: §1 · p. 2
  • The framework simplifies [18] by avoiding recursive sketching, enabling exact rather than approximate leverage-score sampling and generalization to arbitrary TN formats.The scheme in [18] had polynomial dependence on N for CP and tensor ring, compared with exponential dependence in earlier works [19].Source: §1 · p. 2

2 Related Work

Prior sampling-based ALS methods targeted particular decompositions, with earlier approaches facing exponential dependence on tensor modes and [18] reducing it to polynomial dependence for CP and tensor ring. Other work addresses regularized Tucker decomposition or structured sketching, while some sketching operators still require access to all tensor entries.

2 Related Work

  • Sampling-based ALS methods address CP decomposition: uses a mixture of leverage-score and row-norm sampling, while uses leverage-score sampling to reduce each ALS subproblem; [19] proposes leverage-score sampling for tensor-ring ALS subproblems.Source: §2 · p. 2
  • Earlier methods [19] require sample counts scaling exponentially with tensor modes; [18] reduces the dependence to polynomial for CP and tensor ring.For, the stated costs are Ω(R^(N+1)) for CP; for [19], Ω(R^(2N+2)) for tensor ring.Source: §2 · p. 2
  • Structured sketching operators for general TN matrices can require access to all data-tensor entries in each ALS solve, giving at least linear input-size cost.Ma and Solomonik [16] use dense Gaussian-tensor TN sketching operators; the paper also notes efficient sampling for regularized Tucker with Kronecker-product design matrices [9].Source: §2 · p. 3
  • The related-work discussion focuses on sampling-based ALS and directs readers to [18, Sec. 2] and [20, Sec. 1.2] for broader randomized decomposition and structured-sketching surveys.Source: §2 · p. 3

3 Preliminaries

The preliminaries establish notation for tensors and tensor networks, explain their graphical and matrix representations, and introduce leverage-score sampling for least-squares problems.

3.1 General Notation

  • Tensor entries, modes, dimensions, linear indices, pseudoinverses, and common matrix products receive notation used throughout the paper.A tensor is a multidimensional array of real numbers; the notation also distinguishes tensors, matrices, vectors, and scalars.Source: §3.1 · p. 3

3.2 Tensor Networks

  • TN diagrams represent tensors as nodes with dangling edges for modes, while contractions connect the appropriate edges.Figure 1 depicts scalars, vectors, matrices, and a 4-way tensor; Figure 2 depicts contractions and a Tucker decomposition.Source: §3.2 · pp. 3–4, Figure 1 · p. 4, Figure 2 · p. 4
  • In a TN matrix, dangling edges represent row or column modes, whose ordering may be chosen arbitrarily if kept consistent.Figure 3 illustrates a TN matrix; its mode dimensions determine the represented matrix dimensions.Source: §3.2 · p. 5, Figure 3 · p. 5

3.3 Leverage Score Sampling

  • Leverage scores measure design-matrix row importance, and sampling rows from their normalized distribution supports high-probability approximation of least-squares solutions.The sampling matrix draws rows independently according to p(i) = ℓi(A)/rank(A); the stated sample-size condition gives an error bound of (1 + ε)OPT with probability at least 1 − δ.Source: §3.3 · pp. 5–6

4 Proposed Sampling Method

The method samples rows of a tall-and-skinny TN matrix from the exact leverage score distribution without forming the full matrix or probability vector. It computes the Gram pseudoinverse through TN contractions, then draws row indices sequentially by conditioning on earlier indices.

4.1 Computing Φ

  • Contracting the TN representation computes A⊤A, after which its pseudoinverse Φ = (A⊤A)+ is affordable to compute using standard methods.For a wide range of TN matrices, this can be more efficient than forming A densely and multiplying A⊤A.Source: §4.1 · p. 6, Figure 4 · p. 7

4.2 Drawing Samples Efficiently

  • Sequentially sampling each row index conditional on earlier draws enables exact leverage-score sampling without forming the full probability vector.The approach relies on efficiently contracting the TN representations of the Gram matrix and sampling distributions, which is possible for a large class of tensor networks.Source: §4.2 · pp. 7–8
  • For each index, the method computes probabilities conditioned on the previously drawn indices by contracting a TN for the corresponding joint probabilities.Fixing earlier indices reduces their dimensions to 1; the desired probabilities lie on the diagonal of the resulting matrix, and only diagonal entries need be computed.Source: §4.2 · pp. 7–8

5 Application to Tensor Decomposition

The section formulates tensor-network decomposition as an optimization problem solved by alternating least squares, then extends sampling-based ALS to TN formats and compares its computational complexity for CP and tensor ring decompositions.

5 Application to Tensor Decomposition

  • TN formats include CP, Tucker, tensor train, and tensor ring, and represent the factors used to approximate a data tensor.The decomposition is posed as minimizing a Frobenius-norm objective over the network tensors.Source: §5 · p. 9
  • ALS updates one tensor at a time, turning minimization of the decomposition objective into a linear least-squares problem involving the other tensors.The resulting design matrix is itself a TN matrix; for CP and Tucker it takes Khatri–Rao and Kronecker product forms, respectively.Source: §5 · p. 9
  • For an N-mode tensor with mode dimension I, the input has I^N entries, and conventional ALS iterations access them all while forming a design matrix and solving a linear system.These operations contribute to the exponential dependence on N.Source: §5 · p. 9
  • Sampling each ALS least-squares problem by the leverage scores of its TN design matrix yields a sampling-based scheme for any TN decomposition.The framework samples indices, forms the sampled data and design matrices, then solves the sampled problem.Source: §5 · p. 10

5.1 Computational Complexity Examples

  • The complexity analysis compares TNS-CP and TNS-TR with other methods for rank-R decompositions of N-way cubic tensors, using parameter choices required for theoretical guarantees.The comparison is reported in Tables 1 and 2; the supplied passages do not include their cell values.Source: §5.1 · p. 11, Table 1 · p. 12, Table 2 · p. 12
  • For CP and tensor ring, the proposed methods reduce per-iteration dependence on rank relative to [18] by avoiding recursive sketching; other methods have exponential dependence on N.The comparison concerns computational complexity, not total runtime.Source: §5.1 · p. 11

6 Experiments

The feature-extraction experiment decomposes COIL-100 images with CP or tensor ring methods and uses the resulting features for classification. The proposed methods run faster than the corresponding methods in [18], while decomposition errors and most classification accuracies are similar.

6 Experiments

  • The experiment uses 7,200 COIL-100 images arranged as a 7200 × 128 × 128 × 3 tensor, decomposed with rank-25 CP or rank-(5, 5, 5, 5) tensor ring.The images depict 100 objects from 72 angles; each image is 128 × 128 pixels with three color channels.Source: §6 · p. 12
  • For classification, the experiment uses 1-nearest-neighbor with 10-fold cross-validation, training on 90% of the images and testing on the remaining 10%.CP factor-matrix rows serve as image features; tensor ring core slices are reshaped into length-25 feature vectors.Source: §6 · p. 12
  • All methods have roughly the same decomposition error, randomized methods typically have slightly higher error, and all except CPD-NLS yield similar classification accuracy; TNS-CP and TNS-TR are faster than the corresponding methods in [18].Table 3 reports runtime, decomposition error, and classification accuracy.Source: §6 · p. 13, Table 3 · p. 13

7 Conclusion

The conclusion presents a general sampling-based ALS framework for TN decompositions, with exact leverage-score sampling and improved runtime over [18] in CP and tensor ring experiments. It identifies the pseudoinverse cost for general TN matrices as an open efficiency challenge.

7 Conclusion

  • The framework generalizes sampling-based ALS to any TN format, uses exact leverage scores, and improves runtime over [18] for CP and tensor ring in complexity analyses and experiments.The authors characterize their approach as a simplification of the scheme in [18].Source: §7 · p. 13
  • Exact leverage-score sampling for general TN matrices still incurs an Ω(R^3) pseudoinverse cost, and avoiding it remains an open direction.The conclusion notes that such methods are known for certain Kronecker-structured matrices but not for general TN matrices.Source: §7 · p. 13

A Additional Notation

  • The notation appendix defines Kronecker and Khatri–Rao products, identifies Khatri–Rao as columnwise Kronecker, and introduces Hadamard product and tensor Frobenius norm.Source: A Additional Notation · p. 16

B Detailed Complexity Analysis

The detailed analysis breaks down the per-iteration costs for CP and tensor ring sampling-based ALS, including pseudoinverse, sampling, and sampled least-squares steps. It also clarifies guarantee differences and cautions that iteration counts may vary across methods.

B.1 CP Decomposition

  • For CP, computing Φ costs O(NIR^2 + R^3), drawing J samples costs O(JR^2N^2I), and solving the sampled least-squares system costs O(JR(N + R + I)).Each ALS iteration solves N such systems, and the sample bound is J ≳ R max(log(R/δ), 1/(εδ)).Source: §B.1 · pp. 16–17

B.2 Tensor Ring Decomposition

  • For tensor ring, contracting the Gram-matrix network and computing its pseudoinverse costs O(N(R^6 + IR^4)); drawing samples costs O(JN^2IR^6), and solving the sampled system costs O(J(NR^3 + R^4 + IR^2)).The Gram matrix is formed by first contracting large dimensions, then contracting the resulting chain; J ≳ R^2 max(log(R^2/δ), 1/(εδ)).Source: §B.2 · pp. 17–18, Figure 8 · p. 18

B.3 Some Remarks on Tables 1 and 2

  • The table’s randomized methods do not all offer the same guarantee: SPALS has weaker additive-error guarantees, while CP-ARLS-LEV, CP-ALS-ES, and TNS-CP use relative-error guarantees.The tensor ring methods listed use ε and δ in the sense of Theorem 3.3.Source: §B.3 · pp. 18–19
  • Per-iteration cost comparisons do not determine total iterations to a target, since methods may require different numbers of ALS iterations to meet accuracy or termination criteria.The passage notes that deterministic and randomized methods, and different decomposition types, can differ in iteration count.Source: §B.3 · p. 19

C.1 Competing Methods

The comparison includes standard CP and tensor ring ALS methods, minimization variants, and sampling-based alternatives. Sampling-based methods use fixed sample counts, while two embedding-based methods also use recursive sketching.

C.1 Competing Methods

  • CP-ARLS-LEV, CP-ALS-ES [18], and CP-ALS provide CP decomposition comparison methods, with CP-ALS using standard nonrandomized ALS.The CP-ARLS-LEV implementation is by Malik [18], and CP-ALS-ES is the method proposed in [18].Source: §C.1 · p. 19
  • CPD-ALS, CPD-MINF, and CPD-NLS compute CP decompositions using three different minimization approaches.All three are available in Tensorlab.Source: §C.1 · p. 19
  • TR-ALS [31], TR-ALS-Sampled [19], and TR-ALS-ES [18] are compared as tensor ring decomposition methods.TR-ALS is the standard ALS method; the other two are sampling-based and the method proposed in [18], respectively.Source: §C.1 · p. 19

C.2 Parameter Choices

  • Sampling-based CP methods use J = 2000 rows and tensor ring methods use J = 1000 samples; CP-ALS-ES and TR-ALS-ES use embedding dimension 10000.The intermediate embeddings for both methods use recursive sketching, with dimension 10000 as suggested in [18].Source: §C.2 · p. 19

C.3 Hardware/Software and Dataset

The experiments were run in Matlab R2021b on a laptop. The feature extraction experiment used the COIL-100 dataset.

C.3 Hardware/Software and Dataset

  • Experiments ran in Matlab R2021b on a laptop.Source: §C.3 · p. 20
  • The laptop used an Intel Core i7-1185G7 CPU.Source: §C.3 · p. 20
  • The laptop had 32 GB of RAM, and the experiment used the COIL-100 dataset.The dataset is available for download.Source: §C.3 · p. 20
Loading 2210.03828v1…