# Guaranteed Low-Rank Tensor Recovery from Modewise Measurements via Normalized Block-Weighted Riemannian Gradient Descent

arXiv: https://arxiv.org/abs/2609.24679 · HTML: https://mlsanity.com/paper/2609.24679/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 41 references that are in the map.
- First posted on arXiv 21 Sep 2026.

## Builds on (most cited first, 13 of 13)

- [Exact tensor completion using t-SVD](https://mlsanity.com/paper/1502.04689/) (2015)
- [Square Deal: Lower Bounds and Improved Relaxations for Tensor Recovery](https://mlsanity.com/paper/1307.5870/) (2013)
- [On Tensor Completion via Nuclear Norm Minimization](https://mlsanity.com/paper/1405.1773/) (2014)
- [Provable Tensor Factorization with Missing Data](https://mlsanity.com/paper/1406.2784/) (2014)
- [On Polynomial Time Methods for Exact Low Rank Tensor Completion](https://mlsanity.com/paper/1702.06980/) (2017)
- [Statistically Optimal and Computationally Efficient Low Rank Tensor Completion from Noisy Entries](https://mlsanity.com/paper/1711.04934/) (2017)
- [Riemannian preconditioning](https://mlsanity.com/paper/1405.6055/) (2014)
- [Lower Memory Oblivious (Tensor) Subspace Embeddings with Fewer Random Bits: Modewise Methods for Least Squares](https://mlsanity.com/paper/1912.08294/) (2019)
- [Implicit Regularization and Entrywise Convergence of Riemannian Optimization for Low Tucker-Rank Tensor Completion](https://mlsanity.com/paper/2108.07899/) (2021)
- [A Preconditioned Riemannian Gradient Descent Algorithm for Low-Rank Matrix Recovery](https://mlsanity.com/paper/2305.02543/) (2023)
- [Grassmannian Optimization for Online Tensor Completion and Tracking with the t-SVD](https://mlsanity.com/paper/2001.11419/) (2020)
- [Johnson-Lindenstrauss Embeddings with Kronecker Structure](https://mlsanity.com/paper/2106.13349/) (2021)
- [Riemannian preconditioned coordinate descent for low multi-linear rank approximation](https://mlsanity.com/paper/2109.01632/) (2021)

## Abstract (arXiv)

We consider the recovery of low-multilinear-rank tensors from linear measurements and propose an adaptive block-weighted modewise Riemannian gradient descent method. The method combines memory-efficient modewise measurements with a normalized adaptive weighting strategy for the core and factor components of the Riemannian gradient. The weighting improves convergence without increasing the multilinear-rank bound of the search direction or the size of the reduced core used for retraction. Under the tensor restricted isometry property and a suitable initialization, we establish local linear convergence and derive sampling guarantees for sub-Gaussian and subsampled orthogonal with random sign (SORS) measurements. Numerical experiments on synthetic low-Tucker-rank tensors show that the proposed method reduces iteration counts and computational time while maintaining reliable recovery performance, especially near the recovery threshold and for structured SORS measurements.