The complexity of matrix completion

DOI10.1145/1109557.1109679zbMath1192.68322OpenAlexW4248101621MaRDI QIDQ3581565

Nicholas J. A. Harvey, Sergey Yekhanin, David R. Karger

Publication date: 16 August 2010

Published in: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1109557.1109679

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Software, source code, etc. for problems pertaining to linear algebra (15-04)

Related Items

A simultaneous decomposition of a matrix triplet with applications ⋮ Guarantees of Riemannian optimization for low rank matrix completion ⋮ Some optimization problems on ranks and inertias of matrix-valued functions subject to linear matrix equation restrictions ⋮ Iterative rank-one matrix completion via singular value decomposition and nuclear norm regularization ⋮ Matrix completion with sparse measurement errors ⋮ Formulas for calculating the extremum ranks and inertias of a four-term quadratic matrix-valued function and their applications ⋮ Low rank matrix completion by alternating steepest descent methods ⋮ A singular value thresholding with diagonal-update algorithm for low-rank matrix completion ⋮ The two-stage iteration algorithms based on the shortest distance for low-rank matrix completion ⋮ Finding a low-rank basis in a matrix subspace ⋮ Matrix completion under interval uncertainty ⋮ Max-min problems on the ranks and inertias of the matrix expressions \(A - BXC \pm (BXC)^{\ast}\) with applications ⋮ The inverse of any two-by-two nonsingular partitioned matrix and three matrix inverse completion problems ⋮ Toeplitz matrix completion via smoothing augmented Lagrange multiplier algorithm ⋮ Homotopy method for matrix rank minimization based on the matrix hard thresholding method ⋮ Relations between least-squares and least-rank solutions of the matrix equation \(AXB=C\) ⋮ Minimal rank completions for overlapping blocks ⋮ A new method based on the manifold-alternative approximating for low-rank matrix completion ⋮ Generalized Wong sequences and their applications to Edmonds' problems

This page was built for publication: The complexity of matrix completion