PaperlayerView exact revision on arXiv

Source-linked AI summary

Provable Sparse Tensor Decomposition

Will Wei Sun, Junwei Lu, Han Liu, Guang Cheng

arXiv:1502.01425v3stat.ML

TL;DR

High-dimensional tensor decomposition often needs to select informative features, but most existing results use non-sparse components. TTP embeds truncation in tensor power iteration and uses sparse SVD initialization; the paper establishes local and global statistical rates that improve on non-sparse methods in high-dimensional regimes.

  • Problem

    Most existing tensor decomposition results use non-sparse components, although high-dimensional applications need informative-feature selection for structure recovery and interpretability.

    Source: §1 · p. 2

  • Method

    TTP incorporates truncation into tensor power iteration and uses a provable sparse SVD initialization to pursue a global statistical rate.

    Source: §1 · p. 2

  • Results

    In high-dimensional regimes, TTP’s statistical rate improves on rates from non-sparse tensor decomposition methods.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The paper applies TTP to high-dimensional clustering and mixtures of sparse regressions and notes possible adaptation to other high-dimensional latent-variable models.

    Source: §7 · p. 16

    The theoretical analysis assumes identifiability and incoherence of the decomposition.

    Source: §3 · p. 9

Abstract

from arXiv · show

We propose a novel sparse tensor decomposition method, namely Tensor Truncated Power (TTP) method, that incorporates variable selection into the estimation of decomposition components. The sparsity is achieved via an efficient truncation step embedded in the tensor power iteration. Our method applies to a broad family of high dimensional latent variable models, including high dimensional Gaussian mixture and mixtures of sparse regressions. A thorough theoretical investigation is further conducted. In particular, we show that the final decomposition estimator is guaranteed to achieve a local statistical rate, and further strengthen it to the global statistical rate by introducing a proper initialization procedure. In high dimensional regimes, the obtained statistical rate significantly improves those shown in the existing non-sparse decomposition methods. The empirical advantages of TTP are confirmed in extensive simulated results and two real applications of click-through rate prediction and high-dimensional gene clustering.

1 Introduction

Sparse tensor decomposition is motivated by high-dimensional settings where irrelevant features hinder structure recovery and interpretability. The paper introduces Tensor Truncated Power (TTP), establishes local and global statistical rates, and compares its guarantees with non-sparse methods.

1 Introduction

  • Tensor decomposition is used in recommendation, while contextual information such as season can make user-item interactions vary.The introduction motivates representing user, item, and context together as a tensor.Source: §1 · pp. 1–2
  • TTP updates decomposition components with a tensor power step, then truncates each to its s largest-magnitude entries to encourage sparsity.The paper says s is much smaller than the maximum mode dimension d and can be tuned data-driven.Source: §1 · p. 2
  • The method establishes local and global statistical rates, reaching the target rate ϵR in O(log(ϵ0/ϵR)) steps from an appropriate initialization.The rate comprises sample error, reflecting observed-tensor noise, and model error, reflecting decomposition complexity.Source: §1 · pp. 2–3

1.1 Comparison with Related Work

  • In high-dimensional regimes, TTP’s statistical rate improves on non-sparse tensor decomposition methods, including Anandkumar et al. (2014c).The comparison passage attributes the improvement to a smaller sample-error term, η(E, d0 + s) rather than η(E, d).Source: §1 · p. 3, §1.1 · p. 3

1 Introduction

  • The paper applies TTP to high-dimensional clustering and mixtures of sparse regressions, and reports extensive experiments.The introduction also describes click-through-rate prediction and high-dimensional gene clustering as real applications.Source: §1 · p. 3

1.1 Comparison with Related Work

  • Prior sparse tensor methods had empirical variable-selection results but, to the authors’ knowledge, lacked theoretical analysis of their sparse estimators.The paper positions TTP as the first sparse tensor decomposition method with guaranteed local and global statistical rates.Source: §1.1 · p. 4

1.2 Notation

  • The notation section defines vector and matrix norms, supports, index-restricted vectors, tensor products, and generic constants.It also specifies tensor fibers and slices.Source: §1.2 · p. 4

1.3 Paper Organization

  • The paper organization passage assigns Sections 2–6 to the method, theory, tuning, simulations, and a real application, respectively.The supplementary material contains algorithm details, latent-variable applications, additional experiments, and proofs.Source: §1.3 · p. 4

2 Sparse Tensor Decomposition

TTP extends tensor power decomposition with truncation to select sparse components, providing an algorithm for sparse, low-rank tensor approximation.

2.1 Preliminary

  • For a third-order tensor, mode products combine tensor slices, while its spectral norm takes a supremum over unit vectors in all three modes.A fiber is formed by fixing all but one tensor index.Source: §2.1 · p. 5

2.2 Sparse Tensor Decomposition Method

  • TTP updates tensor-power components and truncates each vector to its largest s entries, then normalizes the retained components.The method targets a rank-K decomposition with sparse component vectors; the sparsity levels s1, s2, and s3 govern truncation across modes.Source: §2.2 · p. 6
  • TTP is the first method in this paper’s account to incorporate truncation into tensor decomposition, using a direct ℓ0 cardinality constraint rather than an ℓ1 penalty.The authors state that truncation supports variable selection and improves tensor-structure recovery in high-dimensional settings.Source: §2.2 · p. 6, §2.3 · p. 8

2.3 Algorithm

  • The algorithm alternates component updates across multiple initializations, clusters the resulting tuples into K components, and can tune K and the sparsity levels from data.It offers sparse-SVD and random initializations; the former has a theoretical guarantee, while the latter is described as simple and fast in practice.Source: §2.3 · p. 7

3 Theoretical Analysis

The theoretical analysis establishes local and global statistical guarantees for TTP under stated conditions. Its local analysis uses an initialization within the basin of attraction, while the global result uses sparse-SVD initialization.

3.1 Local Statistical Rate

  • With suitable initialization and bounded perturbation, local recovery error εR has sample-error and incoherence-driven model-error parts; when E=0, it is of order K/d0.The local result also bounds the recovered component weight by O(εR).Source: §3.1 · p. 10
  • In high dimensions, the local rate uses η(E,d0+s) rather than the larger η(E,d) sample error in non-sparse methods.The paper states that this improves on the non-sparse decomposition rate when d0 ≪ d.Source: §3.1 · p. 11

3.2 Global Statistical Rate

  • Sparse-SVD initialization extends the local analysis to a global statistical guarantee, under stronger conditions on K and perturbation and with polynomially many initializations.The global result is established by combining local analysis with error analysis of the sparse-SVD initialization.Source: §3 · p. 8, §3.2 · p. 11

4 Practical Choice of Tuning Parameters

The paper gives practical guidance for selecting TTP’s initialization, iteration, rank, and cardinality parameters.

4.1 The Number of Initializations and The Number of Iterations

  • Experiments suggest L=max{10,K^3} suffices in practice, and iterations can stop by a convergence-based termination condition instead of a prespecified N.The theoretical initialization bound is polynomial in K.Source: §4.1 · p. 12

4.2 Rank and Cardinality Estimation

  • A BIC-type criterion selects the rank K and cardinality levels s1, s2, and s3 from prespecified candidate sets.The procedure chooses the parameter combination minimizing the corresponding BIC.Source: §4.2 · p. 12

5 Simulation Study

The simulations examine TTP’s incoherence condition, tuning procedure, and performance against non-sparse and lasso-based methods. Across the tested scenarios, TTP improves on non-sparse decomposition and has mixed trade-offs against lasso.

5.1 Illustration of TTP Method

  • With rank 10 and sparsity d0 = d/10, incoherence ζ decays polynomially in d0 as dimension ranges from 10 to 1,000.This empirically demonstrates the polynomial bound in Assumption 3.2.Source: §5.1 · p. 13, Figure 2 · p. 14
  • With dimensions 40 × 30 × 20 and true rank 3, the tuning procedure selects rank 3 and a ratio that yields minimal estimation error and best variable-selection performance.The tested ratio grid is 10^{-2} through 10^0 in 0.1 increments.Source: §5.1 · p. 13, Figure 3 · p. 14

5.2 Comparison with Competitive Methods

  • TTP improves estimation and variable selection over non-sparse decomposition in all scenarios, with over 50% improvement in sparse mean-vector estimation.The comparison averages results over 30 replications.Source: §5.2 · p. 15, Table 1 · p. 15
  • Against lasso, TTP has lower component mean errors in all four scenarios, but slightly worse weight errors in two and includes more noisy variables.Both methods identify almost all true important variables.Source: §5.2 · p. 15, Table 1 · p. 15
  • For the million-entry scenario, TTP takes about 30 seconds per replication, matching non-sparse decomposition and exceeding lasso’s 10 seconds.The authors partly attribute the extra time versus lasso to TTP running L initializations rather than K.Source: §5.2 · p. 15
  • In the tested scenarios, recovery becomes harder as rank K increases when dimension is fixed.This pattern agrees with the authors’ theoretical finding that εR increases with K.Source: §5.2 · p. 15

6 Real Data Analysis

The real-data analysis tests sparse tensor decomposition for online-advertising CTR prediction. TTP is reported to outperform linear regression and GBM on training and testing errors.

6 Real Data Analysis

  • The advertising tensor has dimensions 5 × 2 × 100 and about 90% zero entries; data from November 1, 2015 train the model, with November 2 data used for testing.Entries represent CTR by user-age group, device type, and advertisement.Source: §6 · p. 16
  • TTP greatly improves both training and testing errors over linear regression and GBM in the CTR prediction comparison.Table 2 compares regression on flattened tensor data with TTP on the original tensor.Source: §6 · p. 16, Table 2 · p. 16

7 Discussion

The discussion presents TTP as a sparse tensor decomposition method with local and global statistical rates, applied to high-dimensional latent-variable problems and adaptable to other models.

7 Discussion

  • TTP uses a truncation step for sparse tensor decomposition and has established local and global statistical rates.The discussion identifies this as the paper’s central methodological and theoretical contribution.Source: §7 · p. 16
  • The method is applied to high-dimensional clustering and mixtures of linear sparse regressions.Source: §7 · p. 16
  • The authors say TTP can also be adapted to mixed-membership community detection and dictionary learning.Source: §7 · p. 16

S.1 Initialization and Clustering Procedures

The supplementary procedure describes two initializations for TTP and an efficient clustering procedure for generating decomposition components.

S.1 Initialization and Clustering Procedures

  • Sparse SVD initialization has a theoretical guarantee, while random initialization is simple and fast in practice.Source: §S.1 · p. 20
  • The procedure also provides an efficient clustering step to generate all decomposition components.Source: §S.1 · p. 20
  • The two initialization options trade a stated theoretical guarantee for simplicity and speed in practice.Source: §S.1 · p. 20

S.1.1 Initialization Step

The section gives two initialization options for TTP: sparse SVD, with theoretical guarantees, and a faster random procedure whose theory is unclear.

S.1.1 Initialization Step

  • Sparse SVD initialization truncates a Gaussian vector, contracts the tensor along it, then truncates the leading left and right singular vectors.The resulting vectors provide initial decomposition components.Source: §S.1.1 · p. 20
  • Repeating sparse SVD initialization can generate good starting points and is shown to lead to the global statistical rate.The singular-vector spaces need not be orthogonal for this guarantee.Source: §S.1.1 · p. 20
  • Random initialization truncates two standard Gaussian vectors to retain a few largest-magnitude entries, normalizes them, and computes the remaining component from the main update.This procedure is described as efficient in practice, but its theoretical analysis is unclear.Source: §S.1.1 · p. 21

S.1.2 Clustering Step

The clustering procedure selects the strongest candidate, refines it, and removes nearby tuples to recover the K decomposition components. Its distance threshold separates close initializations from distant ones and is not critical within a stated range.

S.1.2 Clustering Step

  • Clustering selects the tuple maximizing the absolute tensor contraction, runs N power iterations, and removes tuples close to the refined component until K components are output.The removal distance accounts for sign reversals in each component vector.Source: §S.1.2 · p. 21
  • Any threshold constant above 10^-4 and below 1 yields the same result in the reported experiments.The authors report that distances were generally either below 10^-4 or greater than 1.Source: §S.1.2 · p. 21
  • The plotted circles encode initialization-to-center distances, with the red line marking the 0.5 threshold; close starts are below the 10^-4 stopping criterion.The figure shows results for components 1, 3, and 5; the other two cases are described as similar.Source: §S.1.2 · pp. 21–22, Figure S4 · p. 22

S.2 Applications of Sparse Tensor Decomposition

The section considers sparse tensor decomposition for two high-dimensional latent-variable models: Gaussian mixtures and mixture linear models.

S.2 Applications of Sparse Tensor Decomposition

  • The applications examine Gaussian mixture and mixture linear models in high-dimensional settings where parameters have sparsity structure.Source: §S.2 · p. 22

S.2.1 Sparse Gaussian Mixture Model

The sparse Gaussian mixture model assumes sparse means and a shared diagonal covariance, and relates its parameters to moments for recovery with sparse tensor decomposition. The method’s success depends on an incoherence condition; a heuristic shift is proposed when it fails.

S.2.1 Sparse Gaussian Mixture Model

  • Each Gaussian mixture component has a sparse mean, and all components share a common diagonal covariance matrix σ^2I.The mean supports need not be identical across components.Source: §S.2.1 · pp. 22–23
  • The model parameters are recovered through empirical moments: covariance yields σ^2, while a third-moment tensor is decomposed to recover weights and means.The decomposition treats each component's three vectors as the same mean vector.Source: §S.2.1 · p. 23
  • For non-unit means, the procedure whitens the second-moment tensor, estimates mixture weights with robust decomposition, then applies sparse decomposition to recover the means.If the estimated second-moment matrix is singular, thresholding is used before eigendecomposition.Source: §S.2.1 · p. 23
  • Sparse decomposition relies on an incoherence condition; when means violate it, the authors suggest a heuristic shift intended to make cluster means nearly orthogonal.The proposed practical shift uses initial means from k-means, and its performance is demonstrated in supplementary experiments.Source: §S.2.1 · pp. 23–24

S.2.2 Mixtures of Linear Sparse Regressions

This section develops a sparse tensor decomposition approach for mixtures of linear sparse regressions, including a soft-thresholding variant and sparse-SVD initialization. It presents simulated and real-data clustering results and outlines proofs and auxiliary lemmas supporting local and global statistical guarantees.

S.2.2 Mixtures of Linear Sparse Regressions

  • The regression method combines spectral experts with sparse tensor decomposition to estimate mixture weights and sparse regression coefficients.It estimates m by lasso and M by low-rank regression, then decomposes the estimated tensor to recover the parameters.Source: §S.2.2 · pp. 24–25

S.3.1 Simulation Study

  • In Model 3, reconstructed samples generated from the estimated clusters mimic the original four-cluster observations well.Figure S5 compares the original and reconstructed samples.Source: §S.3.1 · p. 26, Figure S5 · p. 26
  • Across four simulation models, the method identifies true important variables; true tensors fully recover means and weights only in orthogonal Models 1–2, not Models 3–4.Sample error dominates model error, and the reported error rate improves on Anandkumar et al. (2014c).Source: §S.3.1 · p. 26, Table S1 · p. 27

S.3.2 Real Data Analysis

  • On the Leukemia dataset, the method achieves competitive clustering with substantially fewer selected genes than k-means and regularized k-means.The comparison uses available cancer types as the evaluation criterion.Source: §S.3.2 · p. 27, Table S2 · p. 27

S.4.1 Proof of Theorem 3.6

  • The local proof establishes a one-iteration contraction with a non-contracting error term and a contracting term, then iterates the bound to obtain the desired error rate.The contracting contribution is of order ϵ^2, while larger input or perturbation error worsens the output bound.Source: §S.4.1 · pp. 28–29

S.4.2 Proof of Theorem 3.9

  • The global-rate proof combines sparse SVD initialization and clustering accuracy with the local-rate result; clustering yields centers O(ϵR) close to the true components.The initialization procedure is analyzed to ensure it can produce a starting point close to a true component.Source: §S.4.2 · pp. 29–30

S.5.1 Proof of Lemma S.4.1

  • The detailed one-step proof bounds the dense unnormalized update, the normalized sparse update, and finally the weight-update error.Source: §S.5.1 · p. 31
  • For Lemma S.4.1, the proof combines bounds across three stages to obtain decomposition-component and weight-estimation error rates.The argument bounds the component error and its normalization under a positive lower bound on the update norm.Source: §S.5.1 · pp. 33–34

S.5.2 Proof of Corollary 3.8

  • The Corollary 3.8 proof extends the argument to soft-thresholding by establishing a bound analogous to (S.8), with the remaining steps unchanged.It uses the support of c_j and a threshold based on ρ to show that supported entries remain nonzero after soft-thresholding.Source: §S.5.2 · p. 34

S.5.3 Proof of Lemma S.4.2

  • Repeating the sparse SVD procedure many times can produce good initializations despite the component spaces not being orthogonal.The proof studies the leading singular vectors of a Gaussian-weighted tensor slice and derives a high-probability initialization guarantee under stated conditions.Source: §S.5.3 · pp. 34–35

S.6 Auxiliary Lemmas

  • The cited contraction is unchanged under F, TF ×1 x ×2 y ×3 z = T ×1 x ×2 y ×3 z; for any tensor T ∈ Rd×d×d and unit x,y ∈ Rd, ∥T ×1 x ×2 y∥ ≤ ∥T∥.Source: §S.6 · p. 35
Loading 1502.01425v3…