An application of the Von Neumann algorithm to matrix completion and other data problems

The effectiveness and the convergence of the Von Neumann Algorithm are well established for the case of affine spaces and convex sets. We extend the convergence results to the case of more general sets, whose special case is the convex set. We prove the convergence of the algorithm when it is applied to data problems that include matrix completion, sparse vector recovery, and corrupted audio/Image recovery problems. We present the numerical evidence for the excellent performance of the algorithm in those settings. We also derive bounds (and exact formula in special cases) for the sparsity of a sparsest solution of Sparse Vector Recovery Problem. Such bounds have been unknown till now.