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

Award Information
Agency:
Department of Defense
Branch
n/a
Amount:
$69,748.00
Award Year:
2011
Program:
SBIR
Phase:
Phase I
Contract:
N00014-11-M-0478
Award Id:
n/a
Agency Tracking Number:
N102-183-0161
Solicitation Year:
2010
Solicitation Topic Code:
N102-183
Solicitation Number:
2010.2
Small Business Information
8637 East Dunbar Way, Tucson, AZ, -
Hubzone Owned:
N
Minority Owned:
N
Woman Owned:
N
Duns:
962538646
Principal Investigator:
HarrySchmitt
President
(520) 306-7639
haschmitt11@gmail.com
Business Contact:
HarrySchmitt
President
(520) 306-7639
haschmitt11@gmail.com
Research Institute:
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


SBA logo

Department of Agriculture logo

Department of Commerce logo

Department of Defense logo

Department of Education logo

Department of Energy logo

Department of Health and Human Services logo

Department of Homeland Security logo

Department of Transportation logo

Enviromental Protection Agency logo

National Aeronautics and Space Administration logo

National Science Foundation logo
US Flag An Official Website of the United States Government