Mathematical and Computational Framework for Matrix Completion with Nonuniform Sampling in Resource Constrained Environments

Award Information
Agency: Department of Defense
Branch: Navy
Contract: N00014-11-M-0478
Agency Tracking Number: N102-183-0161
Amount: $69,748.00
Phase: Phase I
Program: SBIR
Awards Year: 2011
Solitcitation Year: 2010
Solitcitation Topic Code: N102-183
Solitcitation Number: 2010.2
Small Business Information
8637 East Dunbar Way, Tucson, AZ, -
Duns: 962538646
Hubzone Owned: N
Woman Owned: N
Socially and Economically Disadvantaged: N
Principal Investigator
 Harry Schmitt
 (520) 306-7639
Business Contact
 Harry Schmitt
Title: President
Phone: (520) 306-7639
Research Institution
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.

* information listed above is at the time of submission.

Agency Micro-sites

US Flag An Official Website of the United States Government