Nonsmooth low-rank matrix factorization

Low-rank matrix factorization has become a central subject in data science and machine learning in recent years. While the exact recovery of a low-rank matrix via convex optimization is well understood, its non-convex counterpart remains elusive. Indeed, the nonsmoothness of the non-convex approach is a significant challenge. By analyzing nonsmooth low-rank matrix factorization, we hope to expand the theoretical underpinnings of non-convex optimization algorithms.There is a well-established body of work on using convex optimization in the context of lowrank matrix recovery. It comes equipped with deep theoretical guarantees of exact recovery and has had a tremendous impact in statistics and optimization. In a word, it says that a low-rank matrix that has been corrupted with arbitrarily large noise, yet in not too many entries, can be recovered with perfect precision. This implies a strong form of robustness to noise which is highly desirable in applications where some of the data may have tampered with, or simply be misreported and inaccurate. One drawback of the convex approach is that it suffers from scalability issues. In order to overcome this, in this proposal we will focus on a non-convex approach that can be solved withhighly efficient local search algorithms such as stochastic gradient descent. We will apply it to various large-scale publicly available datasets.In our preliminary work, we have developed novel techniques in order to analyze nonsmooth and non-convex optimization landscapes. We will build on these to provide strong theoretical guarantees for the non-convex approach. Our first research objective will be to analyze the optimization landscape, with a particular focus on critical points as defined by the Clarke derivative. Building on these insights, our second research objective will be to analyze the convergence properties of a local search algorithm. Our third research objective will focus on providing a probabilistic guarantee of exact recovery based on characteristics of the input data.Low-rank matrix factorization has various applications including principal component analysis, facial recognition, video surveillance, recommender systems and natural language processing. Several of these align well with DoD applications, in particular video surveillance to detect moving objects at high speeds with high precision without making any spatio-temporal assumptions. More generally, non-convex optimization algorithms arise in various branches of engineering (for e.g., operations research, systems and controls) so that our theoretical work will, in the long term, serve to provide convergence guarantees for widely used algorithms. These are crucial in safety critical systems such as aircraft and autonomous vehicles.