Guaranteed Noisy CP Tensor Recovery via Riemannian Optimization on the Segre Manifold
Organizations: Department of Applied and Computational Mathematics and Statistics, University of Notre Dame
Abstract
Recovering a low-CP-rank tensor from noisy linear measurements is a central challenge in high-dimensional data analysis, with applications spanning tensor PCA, scalar-on-tensor regression, tensor-on-tensor regression, and beyond. We exploit the intrinsic geometry of rank-one tensors by casting the recovery task as an optimization problem over the Segre manifold, the smooth Riemannian manifold of rank-one tensors. This geometric viewpoint yields two powerful algorithms: Riemannian Gradient Descent (RGD) and Riemannian Gauss-Newton (RGN), each of which preserves feasibility at every iteration. Under mild noise assumptions, we prove that RGD converges at a local linear rate, while RGN exhibits an initial local quadratic phase followed by linear refinement to the statistical error. Extensive synthetic experiments validate these convergence guarantees and demonstrate the practical effectiveness of our methods.
Figures & tables
| Method | Model | Test RMSE | Test |
|---|---|---|---|
| CP format | |||
| CP-ALS | CP rank | ||
| RRR | CP rank | ||
| RGD | CP rank | ||
| RGN | CP rank | ||
| Other tensor formats | |||
Appendix figures & tables17 assets
Supplementary material from the paper’s appendix.
Appendix
| CP decomposition | CP tensor-on-tensor regression | ||
|---|---|---|---|
| Method | Cost | Method | Cost |
| CP-ALS | CP-ALS | ||
| Orth-ALS | RRR | ||
| ICO | Tucker-RGD | ||
| NLS-GN | Tucker-RGN | ||
| GN-CG | TT-IHT | ||
| Tensor-on-tensor regression | CP decomposition | ||
|---|---|---|---|
| RGD | 15.4 | RGD | 14.9 |
| RGN | 16.8 | RGN | 14.7 |
| CP-ALS | 21.6 | CP-ALS | 22.4 |
| RRR | 338.3 | Hybrid AMDM | 24.5 |
| TT-IHT | 18.6 | Orth-ALS | 27.2 |
| Tucker-RGD | 76.3 | ICO | 28.6 |
| Method | |||||
|---|---|---|---|---|---|
| 30 | RGD | 86 | 84 | 74 | 196 |
| RGN | 32 | 34 | 44 | 234 | |
| CP-ALS | 69 | 62 | 64 | 264 | |
| 10 | RGD | 78 | 63 | 79 | 135 |
| RGN | 38 | 34 | 49 | 180 | |
| CP-ALS | 48 | 71 | 63 | 213 |
| Method | |||||
|---|---|---|---|---|---|
| 30 | RGD | 0 | 103 | 241 | 1290 |
| RGN | 0 | 28 | 68 | 391 | |
| CP-ALS | 0 | 45 | 101 | 543 | |
| NLS-GN | 0 | 30 | 55 | 130 | |
| GN-CG | 0 | 42 | 86 | 174 | |
| CP-ALS+ELS | 0 | 1067 | 2022 | 6253 |
| Method | |||||
|---|---|---|---|---|---|
| 30 | RGD | 1.93 (0.07) | 1.94 (0.16) | 1.88 (0.12) | 1.81 (0.08) |
| RGN | 1.93 (0.07) | 1.94 (0.16) | 1.88 (0.12) | 1.81 (0.08) | |
| CP-ALS | 1.93 (0.07) | 1.94 (0.16) | 1.88 (0.12) | 1.81 (0.08) | |
| RRR | 22.0 (15.1) | 32.6 (37.7) | 23.2 (14.3) | 20.1 (10.9) | |
| Tucker-RGD | 4.58 (6.91) | 3.11 (0.15) | 3.02 (0.11) | 2.94 (0.10) | |
| Tucker-RGN | 4.63 (7.03) | 3.11 (0.15) | 3.02 (0.11) | 2.94 (0.10) |
| CPCA | T-HOSVD | Random | |||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Method | 0 | 3 | 5 | 10 | 20 | 0 | 3 | 5 | 10 | 20 | 0 | 3 | 5 | 10 | 20 | ||
| 30 | 0 | RGD | 176 | 3.78 | 1.97 | 1.93 | 1.93 | 248 | 33.2 | 13.1 | 5.75 | 1.93 | 1000 | 886 | 332 | 174 | 144 |
| RGN | 176 | 1.93 | 1.93 | 1.93 | 1.93 | 248 | 28.6 | 11.4 | 6.75 | 1.93 | 1000 | 887 | 311 | 166 | 136 | ||
| CP-ALS | 176 | 1.94 | 1.93 | 1.93 | 1.93 | 248 | 17.7 | 14.1 | 9.68 | 8.14 | 1000 | 168 | 152 | 93.2 | 48.4 | ||
| 0.25 | RGD | 181 | 3.74 | 1.97 | 1.94 | 1.94 | 254 | 38.5 | 11.9 | 3.54 | 3.54 | 1000 | 971 | 622 | 114 | 73.6 | |
| RGN | 181 | 1.94 | 1.94 | 1.94 | 1.94 | 254 | 33.8 | 9.67 | 5.14 | 3.54 | 1000 | 968 | 597 | 122 | 80.7 | ||
| CPCA | T-HOSVD | Random | |||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Method | 0 | 3 | 5 | 10 | 20 | 0 | 3 | 5 | 10 | 20 | 0 | 3 | 5 | 10 | 20 | ||
| 30 | 0 | RGD | 1.88 | 1.88 | 1.88 | 1.88 | 1.88 | 1.96 | 1.88 | 1.88 | 1.88 | 1.88 | 1000 | 494 | 182 | 176 | 175 |
| RGN | 1.88 | 1.88 | 1.88 | 1.88 | 1.88 | 1.96 | 1.88 | 1.88 | 1.88 | 1.88 | 1000 | 292 | 174 | 139 | 138 | ||
| CP-ALS | 1.88 | 1.88 | 1.88 | 1.88 | 1.88 | 1.96 | 1.88 | 1.88 | 1.88 | 1.88 | 1000 | 95.1 | 85.2 | 85.2 | 70.3 | ||
| 0.25 | RGD | 9.33 | 2.46 | 1.95 | 1.88 | 1.88 | 91.7 | 14.2 | 4.64 | 1.90 | 1.88 | 1000 | 465 | 176 | 153 | 144 | |
| RGN | 9.33 | 1.88 | 1.88 | 1.88 | 1.88 | 91.7 | 1.88 | 1.88 | 1.88 | 1.88 | 1000 | 215 | 164 | 48.1 | 36.8 | ||
| Panel A: iteration | |||||
| Method | 3 | 5 | 10 | 30 | 300 |
| CP-ALS | |||||
| RRR | |||||
| RGD | |||||
| RGN | |||||
| Tucker-RGD | |||||
Tensor Decomposition
Tensor decomposition represents multidimensional data with compact factors, supporting efficient analysis, recovery, and compression.
See all 79 papers