Learning with Noise, Sparse Errors, and Missing Data

We introduce three algorithms for solving problems related to the matrix completion problem, with applications to machine learning problems. The first algorithm is the Affine Low-Rank Matrix Completion algorithm, which can handle noise, outliers, and missing data. It extends convex optimization algorithms for robust matrix completion to work for affine low-rank matrices, which have the form of a low-rank matrix plus an affine shift term in the form a matrix with identical columns.

The second algorithm is the Robust Orthogonal Rank-One Matrix Pursuit algorithm, which extends the Orthogonal Rank-One Matrix Pursuit algorithm by making it robust to outliers. The OR1MP algorithm is a greedy algorithm, which we pair with a greedy approach to identify outliers and then treat them as missing data, which any matrix completion algorithm is already capable of handling.

The third algorithm computes an approximate square distance function by training a neural network on a data set generated by adding noise vectors to data drawn from a smooth manifold. This function can be used to solve manifold learning problems that are a nonlinear extension of the matrix completion problem, and has numerous applications in machine learning, such as classification, projection, and style transfer.