Revisit CP Tensor Decomposition: Statistical Optimality and Fast Convergence

Anru R. Zhang; Julien Chhor; Olga Klopp; Runshi Tang

REVIEW 3 major objections 4 minor 2 cited by

Revisit CP Tensor Decomposition: Statistical Optimality and Fast Convergence

T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper proves that, under incoherence and signal-strength conditions, ALS reaches the minimax CP tensor decomposition error in doubly logarithmic time.

desk verdict Strong new minimax theory for ALS local convergence, but the full TASD-ALS pipeline guarantee hinges on an unproven permutation-alignment step. read the letter →

arxiv 2505.23046 v1 pith:VNSS4LR2 submitted 2025-05-29 stat.ME cs.NAmath.NAmath.STstat.MLstat.TH

Runshi Tang , Julien Chhor , Olga Klopp , Anru R. Zhang This is my paper · ORCID

classification stat.MEcs.NAmath.NAmath.STstat.MLstat.TH MSC 15A6962H2562F12

keywords CPtensordecompositionalternatingleastsquaresminimaxoptimalitynon-asymptoticboundssimultaneousdiagonalizationPCATuckerconvergencerate

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Alternating Least Squares is the standard workhorse for CP tensor decomposition, but until now its statistical guarantees were largely limited to rank-one or orthogonal cases. This paper proves that ALS, when initialized properly, is minimax optimal for noisy CP decomposition of general order, dimensions, and rank: under incoherence and signal-strength conditions, its error drops to the information-theoretic lower bound $\sigma\sqrt{p_{\max}}/\lambda_{\min}$ within $O(\log\log(\lambda_{\min}/(\sigma\sqrt{p_{\max}})))$ iterations. For rank-one tensors the statement is sharper: spectral initialization plus one or two ALS sweeps reaches the optimal error. To supply the needed warm start in the general-rank case, the paper introduces TASD, a Tucker-compression-then-simultaneous-diagonalization initialization, and proves that TASD-ALS is consistent. The result matters because it gives the first non-asymptotic minimax guarantee for ALS in general non-orthogonal, higher-rank settings, explaining the fast convergence empirically observed for near-orthogonal tensors.

What carries the argument

The engine is the closed-form ALS update $\hat{B}_k^{(t+1)} = M_k(Y)(\odot_{i\ne k}\hat{A}_i^{(t)})^\dagger$, with $\odot$ the column-wise Kronecker product, applied cyclically over modes. The proof rewrites the error after one update as a deterministic contraction term plus a noise term $\delta = \|M_1(Z)(\hat{A}_d^{(t)}\odot\cdots\odot\hat{A}_2^{(t)})\|_{1\to2}$; the contraction coefficient is controlled by the mutual coherence $\xi = \max_{k,i\ne j}|a_{k,i}^{\top}a_{k,j}|$, which keeps the Gram matrix $(\hat{A}_d^{(t)}\odot\cdots\odot\hat{A}_2^{(t)})^{\top}(\hat{A}_d^{(t)}\odot\cdots\odot\hat{A}_2^{(t)})$ close to the identity. This produces the quadratic-then-linear recurrence and the two convergence regimes. The other load-bearing component is the TASD initializer: it first compresses the noisy tensor to a core of size $R^d$ by HOOI, then forms two random contractions of that core and applies simultaneous diagonalization to the pencil $M_1(\hat{S}\times w_1)\,M_1(\hat{S}\times w_2)^\dagger$, recovering the loading matrices up to permutation. The random contraction vectors guarantee, with high probability, distinct diagonal entries in $D_1D_2^\dagger$, which is exactly the degeneracy that makes deterministic pencil methods noise-sensitive.

What would settle it

Generate a rank-3 order-3 tensor with orthogonal loading vectors, equal unit singular values, $p_k=30$, and noise level $\sigma=0.1$; Theorem 2 predicts that TASD-ALS attains $\varepsilon_t \le C\,\sigma\sqrt{p_{\max}}/\lambda_{\min}$ within $O(\log\log(\lambda_{\min}/(\sigma\sqrt{p_{\max}})))$ iterations, so recording the per-iteration error over ten sweeps and comparing it with that bound would settle the claim.

Watch

Extended reading notes

Core claim

The paper's central claim is that the ALS iteration contracts the estimation error $\varepsilon_t$ to the minimax rate $c\,\sigma\sqrt{p_k}/\lambda$ with high probability whenever the initialization error satisfies $\varepsilon_0 \lambda_{\max} d R / \lambda_{\min} \lesssim 1$, the loading matrices have mutual coherence $\xi$ below a threshold depending on $d$ and $R$, and the smallest singular value $\lambda_{\min}$ is at least a constant times $\sigma\bigl(\sqrt{p_{\max}}\, d^2 \log d \vee (\lambda_{\max}/\lambda_{\min})\sqrt{d p_{\max}\log d}\,(d+R)\bigr)$. The proof exhibits a two-phase recurrence: while the error is above $(R-1)\xi^{d-1}$, contraction is quadratic; below that level it becomes linear. In the low-coherence regime the total iteration count is $O(\log\log(\lambda_{\min}/(\sigma\sqrt{p_{\max}})))$, and a matching minimax lower bound shows the final error rate cannot be improved. In the rank-one case, Theorem 1 shows that HOSVD initialization followed by one or two ALS sweeps achieves the optimal bound under the weaker signal requirement $|\lambda| \gtrsim \sigma p_{\max}^{d/4}$.

Load-bearing premise

The load-bearing premise is that the true loading vectors are sufficiently incoherent and the weakest signal component is sufficiently strong relative to noise; without both, the contraction inequality driving the fast convergence breaks down and the paper's simulations show ALS can fail.

Editorial extensions

If this is right

For rank-one CP tensors, spectral initialization plus two ALS sweeps reaches the minimax error $\sigma\sqrt{p_{\max}}/|\lambda|$ under signal strength $|\lambda|\gtrsim \sigma p_{\max}^{d/4}$, and one sweep is enough whenever $d$ is bounded.
For general rank, ALS with TASD is a statistically consistent estimator whose final error attains the minimax lower bound; no estimator can do better in the model $Y = X + Z$ with sub-Gaussian noise.
The two-phase analysis identifies coherence $\xi$ as the quantity controlling speed: low coherence gives quadratic contraction and $O(\log\log)$ iteration counts, while moderate coherence gives linear contraction with an additional $\log((R-1)\xi^{d-1}\lambda_{\min}/(\sigma\sqrt{p_{\max}}))$ term.
Because the bounds are non-asymptotic and hold for any order $d$ and rank $R\le p_k$, they cover the undercomplete regime where sequential rank-one deflation strategies provably fail.
The estimated singular values and reconstructed signal inherit the same noise level: $\max_r |\widehat{|\lambda_r|}-|\lambda_r|| \lesssim \sigma\sqrt{p_{\max}}$ and $\|\widehat{X}-X\|_F \lesssim dR\,\sigma\sqrt{p_{\max}}$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The doubly logarithmic iteration count suggests that for near-orthogonal, high-signal tensors the practical bottleneck is initialization cost, not ALS refinement; improving TASD's behavior at large $R$ would matter more than accelerating the inner sweeps.
The proof's dependence on coherence suggests a data-driven diagnostic: estimate the loading coherence after a few ALS sweeps; if $\xi^{d-1}$ is comparable to the target error, the algorithm should be switched to the linear-phase analysis, giving a principled stopping rule.
Because TASD-ALS does not require distinct singular values (the eigengap never enters the bounds), the method should work for equal-strength components where whitening and spectral-subtraction approaches fail; this is testable on tensors with $\lambda_1=\cdots=\lambda_R$.
The TASD idea of diagonalizing random contractions of a small Tucker core could extend to overcomplete models ($R>p_k$) by using a larger Tucker rank, but the current minimax statements are restricted to the undercomplete case and would need new proofs.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

This is a serious paper with two major contributions and one load-bearing gap. What is genuinely new: Theorem 2 gives non-asymptotic local convergence of ALS for general-order, general-rank CP decomposition under sub-Gaussian noise, with the quadratic-then-linear phase structure, and Theorem 3 provides an independent Fano lower bound. Together these make the minimax claim credible. The rank-one theorem, showing optimal error within one or two iterations, is cleaner than anything prior. TASD is a reasonable hybrid, and Theorem 4 at least proves consistency of the recovered column set up to permutation. The proofs are detailed, the lower bound is not circular, and the simulations show TASD-ALS beating CPCA-ICO and random ALS in small controlled settings. The citation pattern looks honest: SECSI, ICO, and the rank-one tensor PCA literature are engaged substantively.

The soft spot is exactly where the stress-test note lands. Corollary 2 requires the TASD output to be correctly permuted, and the paper does not prove that. Section H bounds each mode's estimate only up to its own permutation; different permutations across modes can destroy the Khatri-Rao product structure that Theorem 2's initialization condition depends on. Algorithm 4 is described as the alignment method but has no theorem, and its numerical check in Section A.2 covers small ranks and Gaussian loadings only. So the advertised statement that TASD-ALS achieves the minimax rate is not fully proved. The coherence and signal-strength assumptions are strong but at least explicit and tested; the permutation issue is a genuine missing argument and should have been flagged as an open problem or proved.

Do I believe the paper? Yes, the core local-convergence result and the lower bound look right. But I would want the authors to either prove that Algorithm 4 aligns permutations with high probability under the same conditions, or restate Corollary 2 with the alignment assumption made explicit and visible. As it stands, the paper deserves peer review—this is exactly the kind of work a serious referee should spend time on. I would not cite the full TASD-ALS pipeline result until the alignment step is settled, but I would cite the local convergence and lower bound results, which stand on their own.

Referee Report

3 major / 4 minor

Summary. The paper studies the canonical polyadic (CP) tensor decomposition under a signal-plus-noise model with sub-Gaussian noise. It proves a rank-one upper bound for ALS with spectral initialization (Theorem 1), a local convergence theorem for general rank and order (Theorem 2), and an independent Fano-style minimax lower bound (Theorem 3). It then proposes TASD, a Tucker-compression plus simultaneous-diagonalization initialization method, analyzes its error (Theorem 4) and the underlying HOOI estimator (Theorem 5), and combines these into a global claim that TASD-initialized ALS attains the minimax rate in two convergence phases (Corollary 2). The paper also reports simulations on small tensors supporting the empirical behavior of the proposed pipeline.

Significance. If the full pipeline result were established, this would be a substantial contribution: it gives non-asymptotic, minimax-rate guarantees for ALS in a general-order, general-rank, non-orthogonal CP model, provides a rigorous explanation of the empirically observed two-phase convergence, and proposes a concrete initialization method with theoretical error bounds. The local ALS recurrence in Appendix E is detailed, and the lower bound in Theorem 3 is derived by an independent packing-Fano argument rather than by matching the upper bound. The authors also make their code public, which is a practical strength. However, as detailed below, the central pipeline claim currently rests on an unproven permutation-alignment step, so the advertised global guarantee is conditional rather than fully established.

major comments (3)

[Section 4.4, Corollary 2; Section 4.3, Theorem 4; Section H] The central TASD-ALS guarantee assumes the TASD loading estimates are correctly permuted, but no theorem establishes this. Theorem 4 only bounds, for each mode h separately, min_permutation ||â_{h,r} ± a_{h,π(r)}||; it does not guarantee that one permutation aligns all modes simultaneously. If different modes use different permutations, the Khatri-Rao product (⊙_{i≠k} Â_i) mixes distinct CP components, so the initialization condition (16) in Theorem 2 may fail and the local convergence analysis no longer applies. Algorithm 4 is proposed as the alignment device, but no error bound for its output is proved; the only supporting evidence is the numerical comparison in Section A.2, which covers small ranks and Gaussian loadings and does not exercise the coherence or signal-strength boundaries of Corollary 2. This is a load-bearing issue: either provide a theorem showing that Algorithm 4 (or a suitable variant) recovers a common permutation with controlled error under the conditions of Corollary 2, or state Corollary 2 as a conditional result and do not claim the full TASD-ALS pipeline achieves the minimax rate.
[Section 4.3, Theorem 4; Appendix H, Assumptions 2-5] The statement of Theorem 4 bundles several high-probability events on the random contraction vectors w_{ik} into global conditions, but the proof in Appendix H shows that these events hold only under quite restrictive conditions, including ξ d^3 R^{9/2} < 1 and strong lower bounds on λ_min and λ_Tucker. The final error bound in Theorem 4 contains two terms of different orders, and the second term is then used as the initialization error in Corollary 2. Since Corollary 2 restates a subset of these conditions rather than all of the proof's Assumptions 2-5, it is not transparent whether condition (16) of Theorem 2 is actually satisfied in every case covered by Corollary 2. Please state explicitly how the full set of conditions in Theorem 4 implies the initialization condition of Theorem 2, or adjust the statements so that all required conditions are visible in the main text.
[Section 5, Figures 1-4; Appendix A.2] The simulation study does not test the parameter regimes where the main theorems are proved. The loading matrices in Figure 1 are generated with i.i.d. Uniform[-1,1] entries, giving a specific coherence level, while the theoretical conditions (17) and Cξ d^3 R^{9/2} < 1 impose very small coherence for larger d and R. Figure 4 does vary a controlled coherence parameter, but it is limited to d ∈ {3,5}, R = 3, and does not report the accompanying signal-strength values needed to check conditions (16)-(18) or the TASD conditions of Theorem 4. The numerical evidence is therefore useful as an illustration but does not serve as a substitute for the missing alignment proof in Corollary 2.

minor comments (4)

[Figures 3 and 4 captions] The word 'Propoertion' should be 'Proportion' in both captions.
[Appendix H.1] There is a typo: 'obstained' should be 'obtained'.
[Remark 5, Section 4.4] The phrase 'their final estimation error is lower bounded by α^{1-d} σ√p_max/λ_min' seems to state the wrong direction for a statistical guarantee; if it is an upper bound, please write 'upper bounded', and if it is a lower bound, clarify why this is relevant to the comparison.
[Algorithm 4, Section 4.1] It would help to state explicitly what happens when the rows of the estimated matrix A are not exactly rank-one tensors, since in the noisy case they are only approximately so; the current description relies on the exact low-rank structure and does not specify how the rank-one ALS step should handle approximation error.

Circularity Check

0 steps flagged · score 2.0 of 10

No circular derivation found; the main statistical bounds are proved from stated model assumptions, and the unproven permutation-alignment step is a proof gap, not a circular reduction.

full rationale

The central claims are not circular. Theorem 3's minimax lower bound is obtained by an independent packing-Fano argument and does not rely on ALS or TASD. Theorem 2's local convergence bound follows from an explicit recurrence (Eq. 62) derived from the ALS update and the deterministic inequalities in Appendix E; the assumptions (16)–(18) are structural conditions on coherence, signal strength, and initialization accuracy, not fitted quantities. The final rate sigma*sqrt(p_max)/lambda_min is matched to the lower bound rather than imposed. Theorem 4's TASD guarantee is proved from perturbation bounds for HOOI (Theorem 5, proved in Appendix G), eigenvector perturbation theory, and probabilistic properties of Gaussian contraction vectors; it does not assume the ALS conclusion. Corollary 2 is the composition of Theorems 2 and 4 under the stated condition that the TASD loading matrices have been correctly permuted. That permutation alignment is indeed not proved for Algorithm 4, and Section H only bounds the per-mode distance up to an unknown permutation; this is a genuine completeness gap in the end-to-end claim. However, this is not circularity: Corollary 2 explicitly assumes the alignment, rather than deriving the alignment from the conclusion. The self-citations that appear (e.g., Cai and Zhang 2018 for singular-subspace perturbation bounds, Zhang and Xia 2018 for covering nets and rank-one initialization limits) are used as technical lemmas or contextual comparisons; they are independent published results with stated assumptions that do not include the target CPD-ALS theorem, so they are not load-bearing self-citations. Overall, the derivation chain is self-contained enough that no step reduces to its own inputs by definition or by construction; the score reflects only the presence of minor, non-load-bearing self-citations and the unproven alignment step, which is better classified as a correctness/open-problem concern than as circularity.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper introduces no new physical or mathematical entities; it proposes an algorithm (TASD) and proves theorems under explicit structural assumptions. No free parameters are fitted to data; all constants in the bounds are absolute.

assumptions (4)

standard math Kruskal's theorem guarantees uniqueness of CP decomposition up to permutation and scaling under full column rank conditions.
Used to define the target loading vectors and justify the estimation objective (Section 2, Section 4.2).
standard math Perturbation bounds for singular subspaces, pseudoinverses, and eigen-decompositions (Cai and Zhang 2018; Wedin; Stewart; Xu 2020).
Invoked in the proofs of Theorems 1, 2, 4, and 5 to control noise and estimation errors.
domain assumption The noise tensor Z has i.i.d. sub-Gaussian entries with variance σ².
Core to the signal-plus-noise model (3) and the tail bounds used throughout the proofs.
domain assumption Loading matrices have full column rank and bounded coherence ξ; the signal strength satisfies conditions (16)-(18) in Theorem 2 and the corresponding conditions in Theorem 4.
These structural conditions are necessary for local convergence and for TASD to provide a good initialization. They restrict the theory to moderately incoherent and sufficiently strong signals.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Revisit CP Tensor Decomposition: Statistical Optimality and Fast Convergence." pith.science (2026). https://pith.science/paper/VNSS4LR2

@misc{pith2026250523046,
  author       = {Pith},
  title        = {Pith review of: Revisit CP Tensor Decomposition: Statistical Optimality and Fast Convergence},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VNSS4LR2}},
  note         = {Machine review of arXiv:2505.23046}
}

read the original abstract

Canonical Polyadic (CP) tensor decomposition is a fundamental technique for analyzing high-dimensional tensor data. While the Alternating Least Squares (ALS) algorithm is widely used for computing CP decomposition due to its simplicity and empirical success, its theoretical foundation, particularly regarding statistical optimality and convergence behavior, remain underdeveloped, especially in noisy, non-orthogonal, and higher-rank settings. In this work, we revisit CP tensor decomposition from a statistical perspective and provide a comprehensive theoretical analysis of ALS under a signal-plus-noise model. We establish non-asymptotic, minimax-optimal error bounds for tensors of general order, dimensions, and rank, assuming suitable initialization. To enable such initialization, we propose Tucker-based Approximation with Simultaneous Diagonalization (TASD), a robust method that improves stability and accuracy in noisy regimes. Combined with ALS, TASD yields a statistically consistent estimator. We further analyze the convergence dynamics of ALS, identifying a two-phase pattern-initial quadratic convergence followed by linear refinement. We further show that in the rank-one setting, ALS with an appropriately chosen initialization attains optimal error within just one or two iterations.

Figures

Figures reproduced from arXiv: 2505.23046 by the authors.

**Figure 2.** Scatter (log-scale) of loss versus α for TASD-ALS; solid line shows median. Convergence Speed for Higher-Order Tensors. We next study convergence speed for the high order tensor. In the first setting, we let pk = 5, d ∈ {3, 5, 7}, R = 1 and σ ∈ [0.005, 0.05] [PITH_FULL_IMAGE:figures/full_fig_p024_2.png] view at source ↗

**Figure 3.** Propoertion of number of iterations required by R1-ALS to yield [PITH_FULL_IMAGE:figures/full_fig_p025_3.png] view at source ↗

Figures from the paper (3 more)

**Figure 4.** Figure 4: Propoertion of number of iterations required by TASD-ALS to yield [PITH_FULL_IMAGE:figures/full_fig_p025_4.png]

**Figure 5.** Figure 5: Loss comparison over varying rank R and noise level σ. A.2 Setting 2 We use the same simulation setup as in [PITH_FULL_IMAGE:figures/full_fig_p035_5.png]

**Figure 6.** Figure 6: Loss comparison between Exhaustive Search and the Alternative Procedure (Algorithm [PITH_FULL_IMAGE:figures/full_fig_p036_6.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

A functional tensor model for dynamic multilayer networks with common invariant subspaces and the RKHS estimation
stat.ME 2025-09 unverdicted novelty 6.0 of 10

A functional tensor model with common invariant subspaces and RKHS estimation for analyzing dynamic multilayer networks, applied to bike-share and food-trade data.
A Scalable Factorization Approach for High-Order Structured Tensor Recovery
cs.LG 2025-06 conditional novelty 6.0 of 10

Gradient descent on the Stiefel manifold recovers Tucker and tensor-train tensors with linear convergence whose initialization requirement and rate scale polynomially with the tensor order N.

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages · cited by 2 Pith papers

[1]

If d >3, ε0 + ξ ≤ CdR 1 d−3 −1 , if d = 3, ε0 + ξ ≤ (CR 1/2)−1; (64)

work page
[2]

ε 0 λmax λmin (d + R) ≤ C; (63)

work page
[3]

λ min ≥ C λmax λmin σ p dpmax log d(d + R); (66)

work page
[4]

B Additional Notations We denote Op,r := U ∈ Rp×r : U ⊤U = I as the set of all p-by-r semi-orthonormal matrices, i.e., matrices with orthonormal columns

for the estimated loading matrices by TASD (Algorithm 3). B Additional Notations We denote Op,r := U ∈ Rp×r : U ⊤U = I as the set of all p-by-r semi-orthonormal matrices, i.e., matrices with orthonormal columns. For U ∈ Op,r, U⊥ represents a matrix in Op,p−r whose columns are orthogonal to the columns of U . In this work, we employ the sin Θ distance to c...

work page 2018
[5]

λ min ≥ Cσp 1/2 maxd2 log d; (65)

work page
[6]

(67) where C and c are absolute constants

λmax λmin Rdξd−2 ≤ c. (67) where C and c are absolute constants. 51 E.2.1 Simplify the recurrence formula We first assume εt+1 ≤ εt ≤ ε0 before reaching the desired accuracy level and prove this later during induction. The denominator of (62) is lower bounded as 1 − (R − 1)(ξ + 2εt + ε2 t )d−1 ≥ 1 − (R − 1)(ξ + 3εt)d−1 > c (68) where c is some absolute co...

work page
[7]

If εt ≤ 3ϵ∗, then we are done

Condition (66) guarantees the existence of such solution and monotonicity of εt − ϵ∗. If εt ≤ 3ϵ∗, then we are done. Otherwise, we have εt+1 − ϵ∗ ≤ 2C λmax λmin (d + R)(εt − ϵ∗)2 ≤ ... ≤ 2C λmax λmin (d + R) 2(t−t0)−1 (εt0 − ϵ∗)2(t−t0) , which by condition (66) implies εt+1 ≤ ϵ∗ + 1 2 2t−1 ≲ ϵ∗, for t ≳ log log(ϵ∗)−1. Further note that λ−1 minδ2 ≲ ϵ∗ = 2C...

work page
[8]

λ Tucker ≥ Cσp d/4 max (78)

work page

Show all 13 references

[9]

λ Tucker ≥ Cσd   q rd−1max + vuutlog(d) dX k=1 pkrk   · · ·3d (79)
[10]

Let’s assume σ = 1 without loss of generality

p min > Clog d. Let’s assume σ = 1 without loss of generality. Let Y1 = M1(Y), p−k = Q i̸=k pi, and Lt = maxk sin Θ U (0) k , Uk . The appendix equation (1.16) in Cai and Zhang (2018) yield P ∥U ⊤ 1,⊥Y1PY ⊤ 1 U1∥ ≥x ≤ C exp Cp1 − c min{x2, x q λ2 Tucker + p−1} + C exp −c(λ2 Tu...

2018
[11]

And finally, we have ˆA1 = ˆU1 ˆV1. H.2 Bound on S Furthermore, we have the following to bound the estimated core: ∥S1− ˆS1∥ = ∥M1((S−ˆS)×d k=3w1k)∥ = ∥M1(S−ˆS)[w1d⊗· · ·⊗w13⊗Ip2]∥ ≤ ∥M1(S−ˆS)∥ dY k=3 ∥w1k∥ Note that ∥M1(X ×i−1 k=1 U ⊤ k ×d k=i ˆU ⊤ k − X ×i k=1 U ⊤ k ×d k=i+1...
[12]

By Xu (2020), we have ∥ ˆS† 2 − S† 2∥ ≤3∥S† 2∥∥ ˆS† 2∥∥ ˆS2 − S2∥, which implies ∥ ˆS1 ˆS† 2 − S1S† 2∥ ≤3∥S† 2∥∥ ˆS† 2∥∥ ˆS2 − S2∥∥S1∥ + ∥ ˆS† 2∥∥ ˆS1 − S1∥. (87) Further, note that we have ∥S1∥ ≤ ∥V1∥∥V2∥ max r {|λr dY k=3 ⟨w1k, vr,k⟩|} ≤λmax∥A1∥∥A2∥ max r {| dY k=3 ⟨w1k, vr,...

2020
[13]

Thus, we can let [ x, X] = V1 = OΣA1V ⊤ A1 and we will have κ = κ(V1) = κ(A1), the condition number of A1

We have A = V1DV † 1 where D is a diagonal matrix with diagonal elements Drr = Qd k=3 ⟨w1k,vr,k⟩ ⟨w2k,vr,k⟩ . Thus, we can let [ x, X] = V1 = OΣA1V ⊤ A1 and we will have κ = κ(V1) = κ(A1), the condition number of A1. Plug in (92), we have ∥p∥ ≤ 2κ(A1)∥ ˆS1 ˆS† 2 − S1S† 2∥ minr...

1997

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [1]

If d >3, ε0 + ξ ≤ CdR 1 d−3 −1 , if d = 3, ε0 + ξ ≤ (CR 1/2)−1; (64)

work page

[2] [2]

ε 0 λmax λmin (d + R) ≤ C; (63)

work page

[3] [3]

λ min ≥ C λmax λmin σ p dpmax log d(d + R); (66)

work page

[4] [4]

B Additional Notations We denote Op,r := U ∈ Rp×r : U ⊤U = I as the set of all p-by-r semi-orthonormal matrices, i.e., matrices with orthonormal columns

for the estimated loading matrices by TASD (Algorithm 3). B Additional Notations We denote Op,r := U ∈ Rp×r : U ⊤U = I as the set of all p-by-r semi-orthonormal matrices, i.e., matrices with orthonormal columns. For U ∈ Op,r, U⊥ represents a matrix in Op,p−r whose columns are orthogonal to the columns of U . In this work, we employ the sin Θ distance to c...

work page 2018

[5] [5]

λ min ≥ Cσp 1/2 maxd2 log d; (65)

work page

[6] [6]

(67) where C and c are absolute constants

λmax λmin Rdξd−2 ≤ c. (67) where C and c are absolute constants. 51 E.2.1 Simplify the recurrence formula We first assume εt+1 ≤ εt ≤ ε0 before reaching the desired accuracy level and prove this later during induction. The denominator of (62) is lower bounded as 1 − (R − 1)(ξ + 2εt + ε2 t )d−1 ≥ 1 − (R − 1)(ξ + 3εt)d−1 > c (68) where c is some absolute co...

work page

[7] [7]

If εt ≤ 3ϵ∗, then we are done

Condition (66) guarantees the existence of such solution and monotonicity of εt − ϵ∗. If εt ≤ 3ϵ∗, then we are done. Otherwise, we have εt+1 − ϵ∗ ≤ 2C λmax λmin (d + R)(εt − ϵ∗)2 ≤ ... ≤ 2C λmax λmin (d + R) 2(t−t0)−1 (εt0 − ϵ∗)2(t−t0) , which by condition (66) implies εt+1 ≤ ϵ∗ + 1 2 2t−1 ≲ ϵ∗, for t ≳ log log(ϵ∗)−1. Further note that λ−1 minδ2 ≲ ϵ∗ = 2C...

work page

[8] [8]

λ Tucker ≥ Cσp d/4 max (78)

work page