Deterministic algorithms for matrix completion

DOI10.1002/RSA.20483MaRDI QIDQ2925527zbMATH OpenOpenAlexFDO

Authors Eyal Heiman, Gideon Schechtman, Adi Shraibman

Publication date 16 October 2014

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/rsa.20483

zbMATH Keywords

deterministic guaranteeseigenvalueexpander graphsfactorization normsFrobenius normgraph sparsifiersmatrix completion

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18) Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60) Matrix completion problems (15A83)

Recommendations

• Matrix completion from noisy entries
• Fast and near-optimal matrix completion via randomized basis pursuit
• A simpler approach to matrix completion
• Spectral regularization algorithms for learning large incomplete matrices
• Exact matrix completion via convex optimization

Cites work

• A simpler approach to matrix completion
• Exact matrix completion via convex optimization
• Expander graphs and their applications
• scientific article; zbMATH DE number 4032351 (Why is no real title available?)
• Matrix completion from noisy entries
• Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion
• Ramanujan graphs
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• Twice-Ramanujan sparsifiers

Cited in

(6)

• Sparse random tensors: concentration, regularization and applications
• Long time dynamics for interacting oscillators on graphs
• A divide-and-conquer algorithm for binary matrix completion
• Deterministic tensor completion with hypergraph expanders
• Spectral gap in random bipartite biregular graphs and applications
• Nonconvex deterministic matrix completion by projected gradient descent methods

This page was built for publication: Deterministic algorithms for matrix completion

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