Structured Nuclear Norm Matrix Completion: Guaranteeing Exact Recovery via Block‐Column Scaling

ABSTRACT The goal of low‐rank matrix completion is to minimize the rank of a matrix while adhering to the constraint that known (non‐missing) elements are fixed in the approximation. Minimizing rank is a difficult, non‐convex, NP‐hard problem, often addressed by substituting rank with the nuclear norm to achieve a convex relaxation. We focus on structured matrices for completion, where, in addition to the constraints described earlier, matrices also adhere to a predefined structure. We propose a technique that ensures the exact recovery of missing entries by minimizing the nuclear norm of a matrix where the non‐missing entries are first subject to block‐column scaling. We provide the proofs for exact recovery and propose a way for choosing the scaling parameter to ensure exact recovery. The method is demonstrated in several numerical examples, showing the usefulness of the proposed technique.