Low-rank matrix completion in a general non-orthogonal basis

DOI10.1016/J.LAA.2021.05.001zbMATH Open1470.15023arXiv1812.05786OpenAlexW3157639225MaRDI QIDQ2032243FDOQ2032243

Authors: Abiy Tasissa, Rongjie Lai 

Publication date: 11 June 2021

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Abstract: 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(n^3)$ 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 $u$, under additional mild assumptions, our main result shows that the true matrix can be recovered with very high probability from $O(nrulo{g}^{2}n)$ uniformly random expansion coefficients.

Full work available at URL: https://arxiv.org/abs/1812.05786

Recommendations

• Matrix Completion Based on Non-Convex Low-Rank Approximation
• Orthogonal rank-one matrix pursuit for low rank matrix completion
• A nonconvex approach to low-rank matrix completion using convex optimization.
• Matrix Completion under Low-Rank Missing Mechanism
• Low rank matrix completion by alternating direction method of multipliers
• Low-rank matrix completion using alternating minimization
• A Deterministic Theory of Low Rank Matrix Completion
• An efficient method for non-negative low-rank completion
• Low-rank matrix completion by Riemannian optimization
• Matrix completion for matrices with low-rank displacement

zbMATH Keywords

matrix completionrestricted isometry propertydual basisnuclear norm minimizationoperator Chernoff bounds

Mathematics Subject Classification ID

Matrix completion problems (15A83) Geometric probability and stochastic geometry (60D05) Numerical methods for low-rank matrix approximation; matrix compression (65F55)

Cites Work

• Phaselift: exact and stable signal recovery from magnitude measurements via convex programming
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• Exact matrix completion via convex optimization
• Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• Characterization of the subdifferential of some matrix norms
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• An introduction to matrix concentration inequalities
• Compressed sensing
• User-friendly tail bounds for sums of random matrices
• A Probabilistic and RIPless Theory of Compressed Sensing
• Recovering Low-Rank Matrices From Few Coefficients in Any Basis
• A simpler approach to matrix completion
• Robust Spectral Compressed Sensing via Structured Matrix Completion
• Sensor network localization, Euclidean distance matrix completions, and graph realization
• RIPless compressed sensing from anisotropic measurements
• Phase retrieval via matrix completion
• Unified Theory for Recovery of Sparse Signals in a General Transform Domain
• Exact Reconstruction of Euclidean Distance Geometry Problem Using Low-Rank Matrix Completion
• Solving partial differential equations on manifolds from incomplete interpoint distance
• Fast and provable algorithms for spectrally sparse signal reconstruction via low-rank Hankel matrix completion
• Compressive Sampling Using Annihilating Filter-Based Low-Rank Interpolation
• Using a distributed SDP approach to solve simulated protein molecular conformation problems

Cited In (7)

• Typical and generic ranks in matrix completion
• Low-rank matrix completion using alternating minimization
• Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm
• Matrix completion for matrices with low-rank displacement
• Matrix completion via a low rank factorization model and an augmented Lagrangean succesive overrelaxation algorithm
• Low-Rank Matrix Completion in the Presence of High Coherence
• Low-Complexity Modeling of Partially Available Second-Order Statistics: Theory and an Efficient Matrix Completion Algorithm

Uses Software

• PhaseLift

This page was built for publication: Low-rank matrix completion in a general non-orthogonal basis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2032243)