Structured Gradient Descent for Fast Robust Low-Rank Hankel Matrix Completion
arXiv:2204.03316 · doi:10.1137/22M1491009
Abstract
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.
References in corpus (10)
- Beyond Nyquist: Efficient Sampling of Sparse Bandlimited Signals
- User-friendly tail bounds for sums of random matrices
- Rank-Sparsity Incoherence for Matrix Decomposition
- Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
- Robust Spectral Compressed Sensing via Structured Matrix Completion
- Structured Low-Rank Algorithms: Theory, MR Applications, and Links to Machine Learning
- Rapid Robust Principal Component Analysis: CUR Accelerated Inexact Low Rank Estimation
- Robust CUR Decomposition: Theory and Imaging Applications
- Accelerated Structured Alternating Projections for Robust Spectrally Sparse Signal Recovery
- Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric Low-Rank Matrix Sensing
Cited by in corpus (6)
- Matrix Completion with Cross-Concentrated Sampling: Bridging Uniform Sampling and CUR Sampling
- Robust Tensor CUR Decompositions: Rapid Low-Tucker-Rank Tensor Recovery with Sparse Corruption
- Accelerating Ill-conditioned Hankel Matrix Recovery via Structured Newton-like Descent
- On the Robustness of Cross-Concentrated Sampling for Matrix Completion
- Structured Sampling for Robust Euclidean Distance Geometry
- Randomized Approach to Matrix Completion: Applications in Recommendation Systems and Image Inpainting