Mathematical and Computational Framework for Matrix Completion with Nonuniform Sampling in Resource Constrained Environments Navy SBIR FY2010.2 Sol No.: Navy SBIR FY2010.2 Topic No.: N102-183 Topic Title: Mathematical and Computational Framework for Matrix Completion with Nonuniform Sampling in Resource Constrained Environments Proposal No.: N102-183-0161 Firm: PhyLas 8637 East Dunbar Way Tucson, Arizona 85747 Contact: Harry Schmitt Phone: (520) 306-7639 Web Site: www.phylas.com Abstract: Matrix completion (MC) concerns the problem of recovering a low rank matrix from a given small fraction of its entries. It is a recurring problem in collaborative filtering, dimensionality reduction, and multi-class learning and has a long history in mathematics. While the general problem of finding the lowest rank matrix satisfying a set of equality constraints is NP-hard, there are quite general settings where it is possible to perfectly recover all of the missing entries of a low-rank matrix by solving a convex optimization problem. One of our team (Recht) has shown how this convex programming heuristic can be used to reconstruct most n x n matrices of rank r from most collections of entries, provided that the number of entries exceeds C n r log2n for some small, positive numerical constant C. This work extended mathematical results from compressive sensing, in particular building upon its geometric ideas. We propose a nine month research program with three lines of investigation: (i) extend current MC approaches to incorporate nonuniform sampling matrices and resource constraints; (ii) implementation of on-line MC algorithms; and (iii) extend current MC approaches to incorporate regularization schemes beyond rank and sparsity. Benefits: The availability of computationally efficient Matrix Completion (MC) algorithms (i.e., algorithms that are scalable, decomposable or distributed) with rigorous mathematical performance bounds has the potential to positively impact a wide range of applications of critical importance to the defense and intelligence communities. Uses within the defense community include a variety of sensor signal processing challenges that center on the extraction and exploitation of low-dimensional, information-rich manifolds from high-dimensional sensor data-spaces. Both the defense and intelligence communities have significant interests in maximizing the potential advantages of their highly networked communications and sensor systems. The full exploitation of these networks demands advances in the fusing of heterogeneous information as well as improving the performance of virtually all areas of Information Assurance / Information Operations. The scheduling and allocation of heterogeneous sensor modes has shown significant promise in theoretical studies and high fidelity simulations, so the extension of the MC formalism to handle this dynamic environment should prove valuable for next-generation networked weapon systems. It is often difficult or even infeasible to acquire and process a full collection of sensor measurements on reasonable time horizons. In such situations, real-time subspace tracking via online matrix completion can provide efficient, consistent estimation from a scattered collection of partial measurements. Such tracking algorithms would enable rapid detection of traffic spikes, broken connections, or intrusions in sensor networks. We stress that most defense and intelligence networks are severely constrained in bandwidth, so it is important to develop MC algorithms that can optimize performance in such environments. Finally, we mention some very promising recent work on applying MC techniques to quantum state tomography. Commercial applications are numerous; they include predictive analytics, wireless ad hoc communication networks, distributed sensor motes and quantum Hamiltonian identification. Return