The low-rank matrix completion (LRMC) problem is to find a low rank matrix from
only a subset of its entries. Similar to compressive sensing (CS), LRMC problem
is often solved by convex relaxation. However, while the $\ell_0$-search of CS
reconstruction is conceptually clear, how to perform $\ell_0$-search for LRMC
was unknown. This work focuses on $\ell_0$-search for LRMC. Algorithms and the
related performance guarantees are discussed.