Finite-Iteration Local Dynamics and Warm Starts for Alternating Power Iteration in Spiked Tensor PCA

Yanjin Xiang; Zhihua Zhang

stat.MLJun 2, 2026

Finite-Iteration Local Dynamics and Warm Starts for Alternating Power Iteration in Spiked Tensor PCA

Authors: Yanjin Xiang, Zhihua Zhang

Organizations: Peking University

Abstract

We study simultaneous alternating power iteration for fixed-order asymmetric rank-one spiked tensor models. Our main contribution is a finite-iteration local theory that is independent of any particular initialization. Once the iterates enter a sufficiently small neighborhood of the planted rank-one direction, their error decomposes into a geometrically decaying transient and an intrinsic noise floor caused by fixed orthogonal noise contractions at the planted point. The deterministic finite-sample conditions are stated explicitly, but under a coarse fixed-order multilinear noise event they reduce to a conservative high-signal regime for fixed or slowly expanding local radii. We then separate the warm-start mechanism from any specific spectral construction. A generic one-sweep principle shows that, if a sign-compatible initializer has correlation $γ_N$ , first-sweep noise level $a_N$ , and $a_N/(γ_N^{d-1}ω_{N,d})\to0$ , then one can choose an expanding radius $r_N=o(ω_{N,d})$ for which the first sweep enters the local basin. After entry, the local affine contraction yields convergence to the unique informative local fixed point in that basin. For centered-Gram initialization, we verify the required correlation and same-sample first-sweep noise bound under i.i.d. finite-fourth-moment noise by a signal-preserving noise-only leave-one comparison and an averaged leave-one slice-contraction estimate, which we call a pressed-back estimate. The leave-one comparison keeps the spike fixed and averages over the deleted coordinate, so planted coordinates enter through $\ell_2$ -weighted sums rather than worst-case incoherence bounds.

Explore similar work

May 30, 2026cs.DS

Easy, robust approximate message passing for planted spike models

We present a simple and efficient algorithm for robust approximate message passing (AMP) in the spiked matrix setting. In particular, let

\varepsilon

be a sufficiently small constant, and suppose that

X \in \mathbb R^{n \times n}

is a Gaussian matrix with a planted rank-

1

spike, and

E \in \mathbb R^{n \times n}

is an adversarially chosen matrix supported on an

\varepsilon n \times \varepsilon n

principal minor. Let

v_{\mathrm{AMP}}(X)

be the output of an AMP iteration on the uncorrupted matrix

X

. We give a procedure that, given access only to the corrupted matrix

Y = X + E

, computes a vector

v_{\mathrm{ALG}}(Y)

which is

\tilde{O}(\sqrt{\varepsilon})

-close to

v_{\mathrm{AMP}}(X)

, for any of a class of AMP iterations which includes sparse Principal Component Analysis (PCA), non-negative PCA, and

\mathbb Z_2

synchronization. Our algorithm consists of a spectral pre-processing step combined with a robust spectral initialization procedure; given these inputs, we prove that (perhaps surprisingly) AMP is robust out-of-the-box.

Misha Ivkov, Tselil Schramm

Principal Component Analysis Message Passing Neural Networks Binary Spikes

Ask PDF

May 10, 2026math.NA

Accelerating Power Method with Fast Sketching for Stronger Low-Rank Approximation

The power method is one of the most fundamental tools for extracting top principal components from data through low-rank matrix approximation. Yet, when the target rank is large, the cost of matrix multiplication associated with this procedure becomes a major bottleneck. We develop an algorithmic and theoretical framework for accelerating the power method using fast sketching, which is a popular paradigm in randomized linear algebra. Our framework leads to simple and provably efficient methods for singular value decomposition, low-rank factorization, and Nyström approximation, which attain strong numerical performance on benchmark problems. The key novelty in our analysis is the use of regularized spectral approximation, a property of fast sketching methods which proves more flexible in generalizing power method guarantees than traditional arguments.

Shabarish Chenakkod, Michał Dereziński

Low-Rank Factorization Principal Component Analysis Approximation Power Method

Ask PDF

May 5, 2026stat.ML

Low Rank Tensor Completion via Adaptive ADMM

We consider a novel algorithm, for the completion of partially observed low-rank tensors, as a generalization of matrix completion. The proposed low-rank tensor completion (TC) method builds on the conventional nuclear norm (NN) minimization-based low-rank TC paradigm, by leveraging the alternating direction method of multipliers (ADMM) optimization framework. To that extend the original NN minimization problem is reformulated into multiple subproblems, which are then solved iteratively via closed-form proximal operators, making use of over-relaxation and an adaptive penalty parameter update scheme, to further speed up convergence and improve the overall performance of the method. Simulation results demonstrate the superior performance of the new method in terms of normalized mean square error (NMSE), compared to the conventional state-of-the-art (SotA) techniques, including NN minimization approaches, as well as a mixture of the latter with a matrix factorization approach, while its convergence can be significantly improved by initializing the algorithm with the solution of the SotA.

Niclas Führling, Getuar Rexhepi, Giuseppe Thadeu Freitas de Abreu

Tensor Completion Alternating Direction Method Of Multiplier Spectral Norm Ranking

Ask PDF