# Low-rank Matrix Completion in a General Non-orthogonal Basis

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Dec 2018.

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

- [Localization from structured distance matrices via low-rank matrix recovery](https://mlsanity.com/paper/2311.18076/) (2023)
- [Riemannian Optimization for Non-convex Euclidean Distance Geometry with Global Recovery Guarantees](https://mlsanity.com/paper/2410.06376/) (2024)
- [Euclidean Distance Matrix Completion via Asymmetric Projected Gradient Descent](https://mlsanity.com/paper/2504.19530/) (2025)
- [Provable Non-Convex Euclidean Distance Matrix Completion: Geometry, Reconstruction, and Robustness](https://mlsanity.com/paper/2508.00091/) (2025)

## Abstract (arXiv)

This paper considers theoretical analysis of recovering a low rank matrix given a few expansion coefficients with respect to any basis. The current approach generalizes the existing analysis for the low-rank matrix completion problem with sampling under entry sensing or with respect to a symmetric orthonormal basis. The analysis is based on dual certificates using a dual basis approach and does not assume the restricted isometry property (RIP). We introduce a condition on the basis called the correlation condition. This condition can be computed in time O(n3) and holds for many cases of deterministic basis where RIP might not hold or is NP hard to verify. If the correlation condition holds and the underlying low rank matrix obeys the coherence condition with parameter nu, under additional mild assumptions, our main result shows that the true matrix can be recovered with very high probability from O(nrnulog2n) uniformly random expansion coefficients.