Sharp Analysis of Power Iteration for Tensor PCA

• URL: http://arxiv.org/abs/2401.01047v1
• Date: Tue, 2 Jan 2024 05:55:27 GMT
• Title: Sharp Analysis of Power Iteration for Tensor PCA
• Authors: Yuchen Wu and Kangjie Zhou
• Abstract summary: We investigate the power algorithm for the tensor PCA model introduced in Richard and Montanari 2014. Our contributions are threefold: First, we establish sharp bounds on the number of iterations required for power method to converge to the planted signal. Second, our analysis reveals that the actual threshold for power is smaller than the one conjectured in literature by a polylog(n) factor.
• Score: 1.9571840167193135
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We investigate the power iteration algorithm for the tensor PCA model introduced in Richard and Montanari (2014). Previous work studying the properties of tensor power iteration is either limited to a constant number of iterations, or requires a non-trivial data-independent initialization. In this paper, we move beyond these limitations and analyze the dynamics of randomly initialized tensor power iteration up to polynomially many steps. Our contributions are threefold: First, we establish sharp bounds on the number of iterations required for power method to converge to the planted signal, for a broad range of the signal-to-noise ratios. Second, our analysis reveals that the actual algorithmic threshold for power iteration is smaller than the one conjectured in literature by a polylog(n) factor, where n is the ambient dimension. Finally, we propose a simple and effective stopping criterion for power iteration, which provably outputs a solution that is highly correlated with the true signal. Extensive numerical experiments verify our theoretical results.

Related papers

• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  In this work, we present a robust phase retrieval problem where the task is to recover an unknown signal. Our proposed oracle avoids the need for computationally spectral descent, using a simple gradient step and outliers.
  arXiv  Detail & Related papers  (2024-09-07T06:37:23Z)
• Tensor cumulants for statistical inference on invariant distributions [49.80012009682584]
  We show that PCA becomes computationally hard at a critical value of the signal's magnitude. We define a new set of objects, which provide an explicit, near-orthogonal basis for invariants of a given degree. It also lets us analyze a new problem of distinguishing between different ensembles.
  arXiv  Detail & Related papers  (2024-04-29T14:33:24Z)
• Statistical Estimation in the Spiked Tensor Model via the Quantum Approximate Optimization Algorithm [17.955614278088238]
  The quantum approximate optimization algorithm (QAOA) is a general-purpose algorithm for optimization. We prove that the weak recovery threshold of $1$-step QAOA matches that of $1$-step tensor power iteration. For some $p$ and $q$, the QAOA attains an overlap that is larger by a constant factor than the tensor power overlap.
  arXiv  Detail & Related papers  (2024-02-29T18:50:28Z)
• Sublinear scaling in non-Markovian open quantum systems simulations [0.0]
  We introduce a numerically exact algorithm to calculate process tensors. Our approach requires only $mathcalO(nlog n)$ singular value decompositions for environments with infinite memory.
  arXiv  Detail & Related papers  (2023-04-11T15:40:33Z)
• Lower Bounds for the Convergence of Tensor Power Iteration on Random Overcomplete Models [3.7565501074323224]
  We show that tensorly many steps are necessary for convergence of tensor power iteration to any true component. We prove that a popular objective function for tensor decomposition is strictly increasing along the power iteration path.
  arXiv  Detail & Related papers  (2022-11-07T19:23:51Z)
• Selective Multiple Power Iteration: from Tensor PCA to gradient-based exploration of landscapes [7.648784748888189]
  Selective Multiple Power Iterations (SMPI) is a new algorithm to address the important problem that consists in recovering a spike. We show that these unexpected performances are due to a powerful mechanism in which the noise plays a key role for the signal recovery. These results may have strong impact on both practical and theoretical applications.
  arXiv  Detail & Related papers  (2021-12-23T01:46:41Z)
• Lattice partition recovery with dyadic CART [79.96359947166592]
  We study piece-wise constant signals corrupted by additive Gaussian noise over a $d$-dimensional lattice. Data of this form naturally arise in a host of applications, and the tasks of signal detection or testing, de-noising and estimation have been studied extensively in the statistical and signal processing literature. In this paper we consider instead the problem of partition recovery, i.e.of estimating the partition of the lattice induced by the constancy regions of the unknown signal. We prove that a DCART-based procedure consistently estimates the underlying partition at a rate of order $sigma2 k*
  arXiv  Detail & Related papers  (2021-05-27T23:41:01Z)
• Stochastic Approximation for Online Tensorial Independent Component Analysis [98.34292831923335]
  Independent component analysis (ICA) has been a popular dimension reduction tool in statistical machine learning and signal processing. In this paper, we present a by-product online tensorial algorithm that estimates for each independent component.
  arXiv  Detail & Related papers  (2020-12-28T18:52:37Z)
• A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise [55.45544638410858]
  We study the problem of PAC learning homogeneous halfspaces in the presence of Tsybakov noise. Our algorithm learns the true halfspace within any accuracy $epsilon$.
  arXiv  Detail & Related papers  (2020-10-04T22:19:06Z)
• On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration [115.1954841020189]
  We study the inequality and non-asymptotic properties of approximation procedures with Polyak-Ruppert averaging. We prove a central limit theorem (CLT) for the averaged iterates with fixed step size and number of iterations going to infinity.
  arXiv  Detail & Related papers  (2020-04-09T17:54:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.