Tensorized random projections reduce high-dimensional tensor size efficiently.
problem Efficiently reducing the dimension of very high-dimensional tensors.
method Proposes two tensorized random projection maps using TT and CP decompositions.
result TT format offers superior performance in terms of required random projection size.
Paper studies tensor models using random matrix theory.
problem Analyzing asymmetric order-d spiked tensor models with Gaussian noise.
method Uses variational definition of singular vectors and values, constructs equivalent spiked symmetric block-wise random matrix from tensor contractions.
result Characterizes asymptotic singular values and alignments of singular vectors with true spike components.
Paper optimizes tensor deflation for non-orthogonal signals.
problem Recovering low-rank signals from noisy tensors with correlated components.
method Developed an asymptotic analysis and optimized deflation procedure using random tensor theory.
result Proposed an efficient tensor deflation algorithm that optimizes a parameter introduced in the deflation mechanism.
Study analyzes Hotelling-type tensor deflation for spiked tensors, providing insights into signal and noise.
problem Characterizing singular values and alignments in Hotelling-type tensor deflation.
method Asymptotic study of Hotelling-type tensor deflation in large dimensional regime using random tensor theory.
result Characterization of singular values and alignments at each step of the deflation procedure.
Study on tensor signal estimation from incomplete data.
problem Estimating a rank-one tensor signal from noisy, incomplete data.
method Reduction to random matrix model for spectral analysis.
result Loss of performance due to incomplete data.
New concentration inequalities for tensors with heavy-tailed coefficients.
problem Developing bounds for Euclidean functions of tensors with sub-Weibull distributions.
method Extending concentration inequalities to sub-Weibull random tensors, using new inequalities for heavy-tailed random variables and martingale analysis.
result Established a phase transition between sub-gaussian and heavy-tailed regimes for Euclidean functions of tensors.
Paper refutes conjecture on tensor power iteration convergence in overcomplete models.
problem Understanding convergence of tensor power iteration in overcomplete random tensors.
method Analysis of tensor power iteration dynamics from random initialization.
result Polynomially many steps are necessary for convergence, refutes logarithmic conjecture.
Study analyzes accuracy of tensor deflation in noisy conditions.
problem Analyzing accuracy of tensor deflation in noisy conditions.
method Asymptotic study of Hotelling-type tensor deflation in large tensor dimensions.
result Characterization of estimated singular values and singular vector alignments.
New method approximates high-dimensional probability densities efficiently.
problem Approximating high-dimensional probability densities accurately and efficiently.
method Hierarchical tensor-network approach using randomized SVD and linear equations.
result The method effectively approximates high-dimensional densities with linear complexity.
New method for tensor classification with missing data.
problem Handling incomplete tensor data in high-dimensional classification.
method High-dimensional tensor linear discriminant analysis with TGMM and Tensor LDA-MD.
result Established convergence rates and minimax optimal bounds for misclassification rate.
The subdifferential of convex functions of the singular spectrum of real matrices has been widely studied in matrix analysis, optimization and automatic control theory. Convex analysis and optimization over spaces of tensors is now gaining much interest due to its potential applications to signal processing, statistics…
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.
TTRP method preserves distances in high-dimensional data with reduced storage and speed.
problem Preserving distances in high-dimensional datasets efficiently and accurately.
method Tensor train random projection (TTRP) using TT-ranks of one.
result TTRP is an expected isometric projection with bounded variance.
In previous work, theoretical analysis based on the tensor Restricted Isometry Property (t-RIP) established the robust recovery guarantees of a low-tubal-rank tensor. The obtained sufficient conditions depend strongly on the assumption that the linear measurement maps satisfy the t-RIP. In this paper, by exploiting the…
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.
TEC combines multiple RPSTMs to classify big tensors efficiently.
problem Tensor classification for big data applications.
method Tensor Ensemble Classifier (TEC) using Random Projection-based Support Tensor Machine (RPSTM).
result TEC provides statistically consistent predictions with reduced computational cost.
Smoothed analysis is a powerful paradigm in overcoming worst-case intractability in unsupervised learning and high-dimensional data analysis. While polynomial time smoothed analysis guarantees have been obtained for worst-case intractable problems like tensor decompositions and learning mixtures of Gaussians, such guar…
Tensorized Rademacher projections outperform Gaussian projections in reducing tensor dimensions.
problem Reducing the dimension of high-dimensional tensors for machine learning.
method Tensorized Rademacher random projections using Tensor Train decomposition.
result Tensorized Rademacher projections can replace Gaussian projections in tensor compression.
Paper proposes robust tensor regression method for tensor data analysis.
problem Outliers in tensor data analysis can make existing methods sensitive.
method Nonconvex relaxation of tensor tubal rank in optimization framework.
result Global convergence of proposed estimation algorithm under mild assumptions.
Study on estimating rank-one tensors in noisy data with heavy tails.
problem Estimating rank-one spiked tensors in the presence of heavy tailed errors.
method Analysis of spectral norm of random tensors with iid entries.
result Signal strength requirements for optimal estimation are similar for heavy tailed and Gaussian noise, but vanish for noise with finite fourth moment.
We present a simple, general technique for reducing the sample complexity of matrix and tensor decomposition algorithms applied to distributions. We use the technique to give a polynomial-time algorithm for standard ICA with sample complexity nearly linear in the dimension, thereby improving substantially on previous b…
New algorithms solve tensor problems with random components using SDP.
problem Exact tensor nuclear norm, decomposition, and completion for random tensors.
method Degree-4 Sum of Squares (SOS) semidefinite programs.
result Exact solutions for tensor nuclear norm, decomposition, and completion with random asymmetric components.
This paper conducts a rigorous analysis for provable estimation of multidimensional arrays, in particular third-order tensors, from a random subset of its corrupted entries. Our study rests heavily on a recently proposed tensor algebraic framework in which we can obtain tensor singular value decomposition (t-SVD) that …
Stochastic trace estimation with tensor train random vectors
problem Stochastic trace estimation for large-scale matrices
method Gaussian random tensor train vectors
result Median-of-means variant achieves dimension-independent guarantees
Paper finds formulas for mutual information and MMSE in matrix tensor product problems.
problem High-dimensional inference problems involving matrix tensor products.
method Single-letter formulas for mutual information and MMSE, using new techniques.
result Analytical formulas describe leading order terms in mutual information and MMSE.
In this paper, we provide local and global convergence guarantees for recovering CP (Candecomp/Parafac) tensor decomposition. The main step of the proposed algorithm is a simple alternating rank-1 update which is the alternating version of the tensor power iteration adapted for asymmetric tensors. Local convergence g…
Gradient descent in tensor factorization favors low-rank solutions.
problem Tackling implicit regularization in tensor factorization problems.
method Gradient descent with small random initialization for overparametrized tensor factorization.
result Gradient descent leads to implicit regularization towards low tubal rank solutions.
The paper analyzes tensor recovery from symmetric rank-one measurements using information theory.
problem Recovering tensors with low symmetric rank from symmetric rank-one measurements.
method Covering numbers argument, Carbery-Wright inequality, orthogonal polynomials, Fano's inequality.
result Near-optimal sample complexity bounds for log-concave distributions.
Introduces t-CCS for flexible tensor sampling.
problem Lack of flexibility in tensor sampling methods.
method Tensor Cross-Concentrated Sampling (t-CCS).
result Effective tensor recovery from t-CCS samples.
Efficiently analyzes multidimensional functional data using separable basis functions.
problem Curse of dimensionality in traditional functional data analysis.
method Marginal product basis systems for multidimensional data, tensor decomposition, differential operator-based penalties.
result Efficient estimation of multidimensional functional data representations.
Develops path integral for spiked tensor model dynamics.
problem Dynamics of spiked tensor model with random initial conditions.
method Path integral approach applied to partial differential equations.
result Large-N saddle point equations dominated by melonic diagrams. The paper studies phase transitions in random matrices and tensor unfolding for detecting signals.
problem Phase transitions in singular values and vectors of large random matrices.
method Analysis of singular values and vectors of long rectangular random matrices, and tensor unfolding algorithm for asymmetric rank-one spiked tensor models.
result An exact threshold for tensor unfolding to detect signals, independent of unfolding procedure.
Tensor rank and low-rank tensor decompositions have many applications in learning and complexity theory. Most known algorithms use unfoldings of tensors and can only handle rank up to n⌊p/2⌋ for a p-th order tensor in Rnp. Previously no efficient algorithm can decompose 3rd order ten…
New approach uses random matrix theory to understand tensor estimation performance.
problem Understanding the performance of estimators for low-rank signals in noisy tensors.
method Developed a new approach using random matrix theory to study random tensors.
result Discovered a fixed-point equation that matches the performance of the maximum likelihood estimator.
We study a statistical model for the tensor principal component analysis problem introduced by Montanari and Richard: Given a order-3 tensor T of the form T=τ⋅v0⊗3+A, where τ≥0 is a signal-to-noise ratio, v0 is a unit vector, and A is a random noise tensor, the goal is to recover th…
Estimates metric tensor on neuromanifolds using Fisher information and random methods.
problem Computing the metric tensor on high-dimensional neuromanifolds efficiently and accurately.
method Deterministic bounds and unbiased random estimators based on Hutchinson's trace method.
result An efficient random estimator with bounded standard deviation.
Accelerates signature kernel computation for sequences.
problem Severe computational bottleneck in computing signature kernel.
method Random Fourier features to accelerate signature kernel computation.
result Uniform approximation guarantees for unbiased estimator with linear computation time.
New estimator for tensor weights with improved bias.
problem Estimating tensor weights from noisy data.
method Random matrix theory and KKT conditions.
result Asymptotically unbiased estimator for tensor rank.
We consider the problem of solving mixed random linear equations with k components. This is the noiseless setting of mixed linear regression. The goal is to estimate multiple linear models from mixed samples in the case where the labels (which sample corresponds to which model) are not observed. We give a tractable a…
Tensors play a central role in many modern machine learning and signal processing applications. In such applications, the target tensor is usually of low rank, i.e., can be expressed as a sum of a small number of rank one tensors. This motivates us to consider the problem of low rank tensor recovery from a class of lin…
New tools in nonlinear random matrices improve understanding of the Sum of Squares hierarchy.
problem Improving the Sum of Squares (SoS) hierarchy's performance on average-case problems.
method Developed new tools in nonlinear random matrices and applied them to analyze the SoS hierarchy.
result Subexponential-time SoS lower bounds for various problems, offering evidence for the low-degree likelihood ratio hypothesis.
A new algorithm speeds up CP decomposition for large tensors.
problem Efficiently processing large-scale tensors in real-time.
method Randomized online CP decomposition (ROCP) algorithm.
result ROCP reduces computing time and memory usage significantly.
Spatio-temporal data compression method reduces memory usage.
problem Efficiently storing and analyzing large spatio-temporal datasets.
method Adaptive sampling of tensor slices to compress and preserve structure.
result SkeTenSmooth outperforms other sampling methods in retaining patterns.
A new tensor completion method handles missing data with missing not at random entries.
problem Handling missing data in tensors where the probability of observation depends on other entries.
method Estimate propensities using convex relaxation, then use higher-order SVD with inverse propensities weights.
result Finite-sample error bounds on the completed tensor are provided.
Surveying random sections on Kähler manifolds, leading to metrics.
problem Understanding statistics of random sections on Kähler manifolds.
method Analyzing tensor powers of line bundles.
result Induced metrics from random sections.
Estimates the probability of a random symmetric tensor being close to rank-one.
problem Estimating the probability of a random symmetric tensor being close to rank-one.
method Using Weyl's tube formula and techniques from Random Matrix theory, we study metric invariants of the real Veronese variety.
result Explicit formula for the reach and curvature coefficients of the real Veronese variety with respect to the Bombieri-Weyl metric.
Paper generalizes tensor-train approximation for complex random variables.
problem Characterizing intractable high-dimensional random variables.
method Extends inverse Rosenblatt transform to general reference measures and integrates into deep variable transformation framework.
result Deep inverse Rosenblatt transport significantly expands tensor approximations for complex random variables.
Estimates joint probability distribution from 1-way marginals using low-rank tensors and random projections.
problem Nonparametric estimation of joint probability mass function (PMF) from limited data.
method Low-rank tensor decomposition and random projections to link data to PMF estimation.
result Estimates joint density from 1-way marginals using transformed space and novel algorithm.