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

Award Information
Agency:
Department of Defense
Branch
Navy
Amount:
$69,748.00
Award Year:
2011
Program:
SBIR
Phase:
Phase I
Contract:
N00014-11-M-0478
Agency Tracking Number:
N102-183-0161
Solicitation Year:
2010
Solicitation Topic Code:
N102-183
Solicitation Number:
2010.2
Small Business Information
PhyLas
8637 East Dunbar Way, Tucson, AZ, -
Hubzone Owned:
N
Socially and Economically Disadvantaged:
N
Woman Owned:
N
Duns:
962538646
Principal Investigator:
Harry Schmitt
President
(520) 306-7639
haschmitt11@gmail.com
Business Contact:
Harry Schmitt
President
(520) 306-7639
haschmitt11@gmail.com
Research Institution:
Stub




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.

* information listed above is at the time of submission.

Agency Micro-sites

US Flag An Official Website of the United States Government