Paper studies statistical-computational trade-offs in tensor PCA and related problems.
problem Statistical-computational gap in tensor PCA estimation.
method Derives computational lower bounds using communication complexity.
result Lower bounds specify trade-off among passes, sample size, and memory.
Principal component analysis (PCA) is an unsupervised method for learning low-dimensional features with orthogonal projections. Multilinear PCA methods extend PCA to deal with multidimensional data (tensors) directly via tensor-to-tensor projection or tensor-to-vector projection (TVP). However, under the TVP setting, i…
Efficient algorithm for tensor PCA with improved time complexity.
problem Tensor PCA problem with signal-to-noise ratio constraint.
method Counting specific weighted hypergraphs to solve tensor PCA.
result Algorithm runs in time nC+o(1) for λn−4p signal-to-noise ratio. New algorithms recover sparse tensor principal components efficiently.
problem Recovering sparse tensor principal components from noisy data.
method Family of algorithms interpolating between polynomial-time and exhaustive search, tailored for sparse and highly sparse regimes.
result Our algorithms recover sparse vectors for signal-to-noise ratios beyond previous limits, with time complexity ildeO(np+t). Face recognition is the important field in machine learning and pattern recognition research area. It has a lot of applications in military, finance, public security, to name a few. In this paper, the combination of the tensor sparse PCA with the nearest-neighbor method (and with the kernel ridge regression method) wil…
Study of Langevin dynamics for tensor PCA recovery in high dimensions.
problem Recovering hidden signal vectors (spikes) from noisy Gaussian tensor observations.
method Langevin dynamics approach for nonconvex optimization.
result Sample complexity matches the single-spike case but degrades for all spikes.
Tensor PCA problem analyzed with statistical query lower bounds.
problem Estimating the expected value of a rank-1 tensor from Gaussian samples.
method Sharp analysis of optimal sample complexity in the Statistical Query model.
result SQ algorithms with polynomial query complexity fail in the conjectured hard phase and have sub-optimal sample complexity.
Sharp analysis of power iteration for tensor PCA, improving convergence and stopping criteria.
problem Analyzing the power iteration algorithm for tensor PCA to improve convergence and stopping criteria.
method Sharp bounds on the number of iterations, revealing a smaller algorithmic threshold, proposing a stopping criterion.
result Sharp bounds on the number of iterations required for power method to converge, revealing a smaller algorithmic threshold than previously conjectured.
Paper develops inference methods for low-rank tensors without debiasing.
problem Statistical inference for low-rank tensor models.
method Two-iteration alternating minimization for asymptotic distribution.
result Asymptotic distributions and confidence regions for singular subspaces.
Optimal tensor PCA for estimating factors and loadings in high-dimensional panel data.
problem Estimating factors and loadings in high-dimensional panel data with non-negligible correlations.
method Tensor Principal Component Analysis (TPCA) for estimating factors and loadings in a tensor factor model.
result Simple TPCA is optimal for strong factors and can be improved for weak factors with alternating least-squares iterations.
Unified approach to tensor PCA and related problems using tensor cumulants.
problem Statistical inference on invariant distributions, particularly tensor PCA.
method Definition and analysis of tensor cumulants to unify and extend previous results.
result Unified explanation of hardness and subexponential-time algorithms for tensor PCA.
Develops a new tensor PCA method for analyzing multiple network data.
problem Analyzing multiple large networks for dimensionality reduction.
method Semi-Symmetric Tensor PCA (SS-TPCA) for principal components analysis.
result SS-TPCA achieves the same estimation accuracy as classical matrix PCA, with error proportional to the square root of the number of vertices.
Developing efficient and guaranteed nonconvex algorithms has been an important challenge in modern machine learning. Algorithms with good empirical performance such as stochastic gradient descent often lack theoretical guarantees. In this paper, we analyze the class of homotopy or continuation methods for global optimi…
SGD recovers multiple signal vectors in noisy tensor PCA.
problem Estimating multiple signal vectors from noisy tensor observations.
method Online stochastic gradient descent (SGD) in high dimensions with detailed analysis of correlations.
result Sequential elimination of correlations allows recovery of all spikes from Np−2 samples. For the tensor PCA (principal component analysis) problem, we propose a new hierarchy of increasingly powerful algorithms with increasing runtime. Our hierarchy is analogous to the sum-of-squares (SOS) hierarchy but is instead inspired by statistical physics and related algorithms such as belief propagation and AMP (ap…
DeepTensor uses deep networks to efficiently decompose tensors with improved performance and robustness.
problem Efficiently decomposing tensors with deep learning to capture nonlinear structures.
method Low-rank tensor decomposition using deep generative networks trained to minimize approximation error.
result DeepTensor outperforms classical methods like SVD and PCA in various applications, including image denoising and 3D MRI.
This paper describes a flexible framework for generalized low-rank tensor estimation problems that includes many important instances arising from applications in computational imaging, genomics, and network analysis. The proposed estimator consists of finding a low-rank tensor fit to the data under generalized parametr…
New algorithms improve tensor CP decomposition under mild conditions.
problem Improving tensor CP decomposition with theoretical guarantees under mild incoherence conditions.
method Composite PCA and Concurrent Orthogonalization algorithms.
result Theoretical guarantees and practical superiority over existing methods.
SMPI recovers tensor spikes from noisy data with improved performance.
problem Recovering tensor spikes corrupted by Gaussian noise.
method Selective Multiple Power Iterations (SMPI) with polynomial random initializations and symmetrized tensor power iterations.
result SMPI outperforms existing algorithms and approaches theoretical optimal recovery.
Non-asymptotic tail bounds for Kostlan-Shub-Smale field on sphere
problem Estimating rank-R symmetric signal tensor from Gaussian observation
method Profile maximum likelihood estimator
result Finite-(k,d) error bound recovers asymptotically optimal rate
High-dimensional tensors or multi-way data are becoming prevalent in areas such as biomedical imaging, chemometrics, networking and bibliometrics. Traditional approaches to finding lower dimensional representations of tensor data include flattening the data and applying matrix factorizations such as principal component…
A simple self-supervised model for tensor RPCA using deep unfolding.
problem Tensor robust principal component analysis (RPCA) challenges in practical applications.
method Deep unfolding with only four hyperparameters.
result Competitive or superior performance compared to supervised methods, even in data-starved scenarios.
Statistical query algorithms and low-degree tests are nearly equivalent in high-dimensional hypothesis testing.
problem High-dimensional hypothesis testing and information-computation gaps.
method Analysis of statistical query framework and low-degree polynomials.
result Statistical query algorithms and low-degree polynomials are almost equivalent in power under mild conditions.
New local-search methods close the gap in sparse tensor PCA.
problem Sparse tensor PCA underperforms compared to other methods.
method Proposes new local-search methods including greedy and random-threshold variants.
result Proves local-search methods close the gap to best known polynomial-time procedures.
Unified framework for statistical inference of low-rank tensors.
problem Statistical inference for tensors in high-dimensional data.
method Unified framework using debiasing and tangent space projection.
result Achieves asymptotic normality and minimax-optimal confidence intervals.
New algorithm improves heteroskedastic PCA performance.
problem Estimating low-rank matrix subspace from noisy data.
method Deflated-HeteroPCA algorithm, dividing spectrum into subblocks.
result Near-optimal and condition-number-free statistical guarantees.
Fourier PCA is Principal Component Analysis of a matrix obtained from higher order derivatives of the logarithm of the Fourier transform of a distribution.We make this method algorithmic by developing a tensor decomposition method for a pair of tensors sharing the same vectors in rank-1 decompositions. Our main appli…
Optimizing over the set of orthogonal matrices is a central component in problems like sparse-PCA or tensor decomposition. Unfortunately, such optimization is hard since simple operations on orthogonal matrices easily break orthogonality, and correcting orthogonality usually costs a large amount of computation. Here we…
Principal component analysis (PCA) is a useful tool when trying to construct factor models from historical asset returns. For the implied volatilities of U.S. equities there is a PCA-based model with a principal eigenportfolio whose return time series lies close to that of an overarching market factor. The authors show…
A tensor network is a diagram that specifies a way to "multiply" a collection of tensors together to produce another tensor (or matrix). Many existing algorithms for tensor problems (such as tensor decomposition and tensor PCA), although they are not presented this way, can be viewed as spectral methods on matrices bui…
We study rank-1 {L1-norm-based TUCKER2} (L1-TUCKER2) decomposition of 3-way tensors, treated as a collection of N D×M matrices that are to be jointly decomposed. Our contributions are as follows. i) We prove that the problem is equivalent to combinatorial optimization over N antipodal-binary variables. ii)…
Robust tensor CP decomposition involves decomposing a tensor into low rank and sparse components. We propose a novel non-convex iterative algorithm with guaranteed recovery. It alternates between low-rank CP decomposition through gradient ascent (a variant of the tensor power method), and hard thresholding of the resid…
The recent proposed Tensor Nuclear Norm (TNN) [Lu et al., 2016; 2018a] is an interesting convex penalty induced by the tensor SVD [Kilmer and Martin, 2011]. It plays a similar role as the matrix nuclear norm which is the convex surrogate of the matrix rank. Considering that the TNN based Tensor Robust PCA [Lu et al., 2…
New tensor recovery method uses Riemannian optimization on Segre manifold.
problem Recovering low-rank tensors from noisy measurements.
method Riemannian Gradient Descent (RGD) and Riemannian Gauss-Newton (RGN) algorithms over the Segre manifold.
result Proven convergence rates for RGD and RGN under mild noise assumptions.
Paper develops RGN method for estimating low-rank tensors from noisy measurements.
problem Estimating low-rank tensors from noisy linear measurements.
method Riemannian Gauss-Newton (RGN) method for efficient low-rank tensor estimation.
result First local quadratic convergence guarantee of RGN for low-rank tensor estimation in noisy settings.
In many high-dimensional estimation problems the main task consists in minimizing a cost function, which is often strongly non-convex when scanned in the space of parameters to be estimated. A standard solution to flatten the corresponding rough landscape consists in summing the losses associated to different data poin…
Neural networks learn faster with correlated latent variables.
problem Efficiently learning from higher-order correlations in neural networks.
method Analytical derivation and simulations of two-layer neural networks.
result Correlations between latent variables speed up learning from higher-order correlations.
Paper proposes a new method for exact recovery in robust tensor principal component analysis.
problem Exact recovery of low-rank and sparse components in tensors.
method Proposes a new method based on tensor-tensor product and t-SVD to solve a convex optimization problem.
result Exact recovery achieved in a deterministic fashion without randomness assumptions.
A distributed framework for reducing high-dimensional matrix-variate time series data.
problem Reducing dimensionality of high-dimensional, heterogeneous matrix-variate time series data.
method Data partitioning, distributed two-dimensional tensor PCA, aggregation, final PCA, factor matrix computation.
result Preserves latent matrix structure, improves computational efficiency and information utilization.
Spectral learning extends matrix methods to tensors for better latent variable modeling.
problem Limitations of matrix-based spectral methods in capturing non-Gaussian data.
method Extend spectral decomposition to tensor-based methods for higher-order moments.
result Tensor decomposition can identify latent effects missed by matrix methods.
We propose a new framework for the analysis of low-rank tensors which lies at the intersection of spectral graph theory and signal processing. As a first step, we present a new graph based low-rank decomposition which approximates the classical low-rank SVD for matrices and multi-linear SVD for tensors. Then, building …
New algorithms recover signals robustly against outliers and heavy-tailed noise.
problem Estimating signals in the presence of heavy-tailed noise and outliers.
method Sum-of-squares relaxations for robust estimation.
result Recovery of signals in polynomial/quasipolynomial time for specific problems.
In many signal processing and machine learning applications, datasets containing private information are held at different locations, requiring the development of distributed privacy-preserving algorithms. Tensor and matrix factorizations are key components of many processing pipelines. In the distributed setting, diff…
Robust TOT regression method handles outliers in tensor data.
problem Outliers in tensor data affect standard TOT regression.
method ROTOT method using a single loss function for outliers and robust MPCA for predictor.
result ROTOT method reduces influence of both casewise and cellwise outliers.
Improved SGD learning for single index models reduces sample complexity.
problem Learning a single index model with optimal sample complexity.
method Using smoothed loss in online SGD to reduce sample complexity.
result Online SGD with smoothed loss achieves optimal sample complexity of dk⋆/2. Study efficient power iteration for tensor models, proving convergence under specific conditions.
problem Simultaneous alternating power iteration for fixed-order asymmetric rank-one spiked tensor models.
method Finite-iteration local theory, geometrically decaying transient, fixed-order multilinear noise event, warm-start mechanism.
result Convergence to the unique informative local fixed point under specific conditions.
New insights into SGD and SGD-M in high dimensions.
problem Understanding and comparing SGD and SGD-M in high-dimensional settings.
method Developed high-dimensional scaling limits for SGD-M and online SGD, examining their dynamics and performance.
result SGD-M amplifies high-dimensional effects, potentially degrading performance compared to online SGD.
New robust MPCA method handles casewise and cellwise outliers in tensor data.
problem Outliers, especially casewise and cellwise, affect the performance of standard MPCA.
method Uses a single loss function to reduce the influence of both types of outliers and missing values.
result The new method improves robustness and performance in tensor data analysis.