Research map / Learning theory and algorithms / Matrix and tensor methods
Non-Convex Tensor Recovery from Local Measurements
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes local tensor compressed sensing where each lateral slice is measured by its own independent sensing matrices, and recovers low-tubal-rank tensors via nonconvex factorization with alternating projected GD and exact minimization (Alt-PGD-Min), plus a preconditioned variant (Alt-ScalePGD-Min) with kappa-independent linear convergence.
Problem
Recovering a low-tubal-rank tensor when the entire tensor cannot be sensed at once, so measurements come only from local lateral-slice sensing (e.g., distributed or streaming video), with provable guarantees and efficient computation.
Approach
Model measurements as independent per-lateral-slice sensing matrices, reparameterize the tensor as a t-product of two compact factors with an orthogonality constraint on one factor, and solve by alternating exact least squares for one factor with projected gradient steps (optionally preconditioned by (V*V^c)^{-1}) for the other, after truncated spectral initialization and sample splitting.
Key results
- Alt-PGD-Min and Alt-ScalePGD-Min show linear convergence on synthetic data while LRcCS fails in all tested kappa settings (kappa=1,2,4).
- Theory: Alt-PGD-Min needs O(kappa^2 log(1/eps)) iterations; Alt-ScalePGD-Min needs O(log(1/eps)) iterations independent of kappa.
- On video CS with r=10, Alt-ScalePGD-Min reaches the best recovery fastest (around 20 iterations), while Alt-PGD-Min and LRcCS converge very slowly even after 8000 iterations.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| precondition the gradient update with the inverse of the factor Gram tensor | Alt-PGD-Min · Local TCS | iteration complexity: \mathcal O\left( \kappa^2 \log \frac{1}{\epsilon}\right) -> \mathcal O(\log \frac{1}{\epsilon}) | Helped |
| precondition the gradient update with the inverse of the factor Gram tensor | Alt-PGD-Min · Local TCS | sample complexity: \mathcal O\left( \kappa^6rn_3\log n_3 \left( \kappa^2r\left(n_1 + n_2 \right) + n_1 \log \frac{1}{\epsilon}\right) \righ | Helped |
| increase tensor condition number κ | Alt-PGD-Min · Synthetic tensor, spectral initialization | convergence rate | Hurt |
| increase tensor condition number κ | Alt-ScalePGD-Min · Synthetic tensor, spectral initialization | convergence rate | No clear effect |
| use LRcCS instead of the tensor recovery methods | Synthetic tensor, spectral initialization · Synthetic tensor, κ=1,2,4 | relative recovery error | Hurt |
| use random initialization instead of spectral initialization (ablation) | Alt-PGD-Min · Synthetic tensor, random initialization | convergence rate | Mixed |
| use random initialization instead of spectral initialization (ablation) | Alt-ScalePGD-Min · Synthetic tensor, random initialization | convergence rate | Mixed |
| increase tensor condition number κ | Alt-PGD-Min · Synthetic tensor, random initialization | convergence rate | Hurt |
| increase tensor condition number κ | Alt-ScalePGD-Min · Synthetic tensor, random initialization | convergence rate | No clear effect |
| use Alt-ScalePGD-Min instead of Alt-PGD-Min | Video compressed sensing · Plane video | convergence rate | Helped |
| use Alt-PGD-Min instead of LRcCS | Video compressed sensing · Plane video | relative recovery error | Hurt |
Surprising findings
- On the video data, Alt-PGD-Min underperforms LRcCS at equal iterations, although it beats LRcCS on synthetic data, which the authors attribute to large tensor condition number in the video.
Limitations
- Requires sample splitting across 2T+1 independent groups, which the authors note is an artifact of the analysis
- Needs spectral initialization; global convergence under random initialization is not established
- Video experiments use only approximately low-tubal-rank data, where the proposed method is slower than LRcCS at equal iterations
Experimental setup
Datasets: synthetic low-tubal-rank tensors (n1=n3=20, n2=400, r=4) plane video sequence (105 frames resized to 48x64)
Benchmarks: synthetic low-tubal-rank tensor recovery plane video compressed sensing
Metrics: relative recovery error vs iteration
Baselines: LRcCS TNN IR-t-TNN FGD
Builds on: matrix sensing with local column measurements (LRcCS) t-SVD / t-product tensor framework factored gradient descent for low tubal rank tensors truncated spectral initialization
Closest papers by meaning
- Non-Convex Tensor Recovery from Tube-Wise Sensing (NeurIPS 2025 · similarity 0.93)
- Robust High-Order Tensor Compressive Sensing Based on M-Estimators (AAAI 2026 · similarity 0.91)
- Nonconvex Low-Rank Tensor Completion from Noisy Data (NeurIPS 2019 · similarity 0.90)
- Algorithmic Regularization in Tensor Optimization: Towards a Lifted Approach in Matrix Sensing (NeurIPS 2023 · similarity 0.90)
- Nonlocal Low-Rank Tensor Factor Analysis for Image Restoration (CVPR 2018 · similarity 0.89)
- Tensor Completion Made Practical (NeurIPS 2020 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.