# Structured Gradient Descent for Fast Robust Low-Rank Hankel Matrix Completion

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Apr 2022.

## Built on by (most cited first, 11 of 11)

- [Matrix Completion with Cross-Concentrated Sampling: Bridging Uniform Sampling and CUR Sampling](https://mlsanity.com/paper/2208.09723/) (2022)
- [Robust Tensor CUR Decompositions: Rapid Low-Tucker-Rank Tensor Recovery with Sparse Corruption](https://mlsanity.com/paper/2305.04080/) (2023)
- [Riemannian CUR Decompositions for Robust Principal Component Analysis](https://mlsanity.com/paper/2206.09042/) (2022)
- [On the Robustness of Cross-Concentrated Sampling for Matrix Completion](https://mlsanity.com/paper/2401.15566/) (2024)
- [Symmetric Matrix Completion with ReLU Sampling](https://mlsanity.com/paper/2406.05822/) (2024)
- [Accelerating Ill-conditioned Hankel Matrix Recovery via Structured Newton-like Descent](https://mlsanity.com/paper/2406.07409/) (2024)
- [Structured Sampling for Robust Euclidean Distance Geometry](https://mlsanity.com/paper/2412.10664/) (2024)
- [Learning Transition Operators From Sparse Space-Time Samples](https://mlsanity.com/paper/2212.00746/) (2022)
- [Euclidean Distance Matrix Completion via Asymmetric Projected Gradient Descent](https://mlsanity.com/paper/2504.19530/) (2025)
- [Randomized Approach to Matrix Completion: Applications in Recommendation Systems and Image Inpainting](https://mlsanity.com/paper/2403.01919/) (2024)
- [Robust Low-Tubal-Rank Tensor Completion under Cross-Concentrated Sampling](https://mlsanity.com/paper/2608.03928/) (2026)

## Abstract (arXiv)

We study the robust matrix completion problem for the low-rank Hankel matrix, which detects the sparse corruptions caused by extreme outliers while we try to recover the original Hankel matrix from the partial observation. In this paper, we explore the convenient Hankel structure and propose a novel non-convex algorithm, coined Hankel Structured Gradient Descent (HSGD), for large-scale robust Hankel matrix completion problems. HSGD is highly computing- and sample-efficient compared to the state-of-the-arts. The recovery guarantee with a linear convergence rate has been established for HSGD under some mild assumptions. The empirical advantages of HSGD are verified on both synthetic datasets and real-world nuclear magnetic resonance signals.