Robust Low-rank Tensor Train Recovery
Not on the map. Why?
Abstract (arXiv)
Tensor train (TT) decomposition represents an N-order tensor using O(N) matrices (i.e., factors) of small dimensions, achieved through products among these factors. Due to its compact representation, TT decomposition has found wide applications, including various tensor recovery problems in signal processing and quantum information. In this paper, we study the problem of reconstructing a TT format tensor from measurements that are contaminated by outliers with arbitrary values. Given the vulnerability of smooth formulations to corruptions, we use an ℓ1 loss function to enhance robustness against outliers. We first establish the ℓ1/ℓ2-restricted isometry property (RIP) for Gaussian measurement operators, demonstrating that the information in the TT format tensor can be preserved using a number of measurements that grows linearly with N. We also prove the sharpness property for the ℓ1 loss function optimized over TT format tensors. Building on the ℓ1/ℓ2-RIP and sharpness property, we then propose two complementary methods to recover the TT format tensor from the corrupted measurements: the projected subgradient method (PSubGM), which optimizes over the entire tensor, and the factorized Riemannian subgradient method (FRSubGM), which optimizes directly over the factors. Compared to PSubGM, the factorized approach FRSubGM significantly reduces the memory cost at the expense of a slightly slower convergence rate. Nevertheless, we show that both methods, with diminishing step sizes, converge linearly to the ground-truth tensor given an appropriate initialization, which can be obtained by a truncated spectral method.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 39 of its 90 references that are in the map. First posted on arXiv 19 Oct 2024.
Builds on
39 of 90 references.
References · 39
- 2016Tensor Decomposition for Signal Processing and Machine Learningcited by 223
- 2014Phase Retrieval via Wirtinger Flow: Theory and Algorithmscited by 123
- 2015Low-rank Solutions of Linear Matrix Equations via Procrustes Flowcited by 97
- 2021Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstructioncited by 77
- 2020Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descentcited by 70
- 2017Tensor SVD: Statistical and Computational Limitscited by 52
- 2015Incremental Gradient, Subgradient, and Proximal Methods for Convex Optimization: A Surveycited by 44
- 2020An Optimal Statistical and Computational Framework for Generalized Tensor Estimationcited by 39
- 2019Nonconvex Low-Rank Tensor Completion from Noisy Datacited by 35
- 2022Algorithmic Regularization in Model-free Overparametrized Asymmetric Matrix Factorizationcited by 34
- 2023The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensingcited by 32
- 2019Low-rank matrix recovery with composite optimization: good conditioning and rapid convergencecited by 31
27 more
- 2014Multilinear tensor regression for longitudinal relational datacited by 28
- 2021Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurementscited by 28
- 2020Low-Rank Matrix Recovery with Scaled Subgradient Methods: Fast and Robust Convergence Without the Condition Numbercited by 27
- 2017Solving (most) of a set of quadratic equalities: Composite optimization for robust phase retrievalcited by 24
- 2016Non-Convex Projected Gradient Descent for Generalized Low-Rank Tensor Regressioncited by 23
- 2021Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recoverycited by 21
- 2022Global Convergence of Sub-gradient Method for Robust Matrix Recovery: Small Initialization, Noisy Measurements, and Over-parameterizationcited by 21
- 2013Exact and Stable Covariance Estimation from Quadratic Sampling via Convex Programmingcited by 20
- 2015Parsimonious Tensor Response Regressioncited by 20
- 2021Provable Tensor-Train Format Tensor Completion by Riemannian Optimizationcited by 17
- 2022Tensor-on-Tensor Regression: Riemannian Optimization, Over-parameterization, Statistical-computational Gap, and Their Interplaycited by 15
- 2018Sparse and Low-rank Tensor Estimation via Cubic Sketchingscited by 11
- 2023Robust Tensor CUR Decompositions: Rapid Low-Tucker-Rank Tensor Recovery with Sparse Corruptioncited by 11
- 2017Nonconvex Low-Rank Matrix Recovery with Arbitrary Outliers via Median-Truncated Gradient Descentcited by 10
- 2020Fast and robust quantum state tomography from few basis measurementscited by 10
- 2020Reduced-Rank Tensor-on-Tensor Regression and Tensor-variate Analysis of Variancecited by 10
- 2019Iterative Hard Thresholding for Low CP-rank Tensor Modelscited by 9
- 2023Quantum State Tomography for Matrix Product Density Operatorscited by 9
- 2022A Validation Approach to Over-parameterized Matrix and Image Recoverycited by 8
- 2024Guaranteed Nonconvex Factorization Approach for Tensor Train Recoverycited by 8
- 2021Tensor train completion: local recovery guarantees via Riemannian optimizationcited by 6
- 2016Median-Truncated Nonconvex Approach for Phase Retrieval with Outlierscited by 4
- 2024Computational and Statistical Guarantees for Tensor-on-Tensor Regression with Tensor Train Decompositioncited by 4
- 2018A theory on the absence of spurious solutions for nonconvex and nonsmooth optimizationcited by 3
- 2019Composite optimization for robust blind deconvolutioncited by 3
- 2023Low-Rank Tensor Completion via Novel Sparsity-Inducing Regularizerscited by 3
- 2014Anomaly detection in reconstructed quantum states using a machine-learning techniquecited by 1
Built on by
Citing papers per year: 2025: 1; 2026: 1.
2 papers.