You are here

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
Solicitation Topic Code: N102-183
Solicitation Number: 2010.2
Timeline
Solicitation Year: 2010
Award Year: 2011
Award Start Date (Proposal Award Date): 2010-10-18
Award End Date (Contract End Date): N/A
Small Business Information
8637 East Dunbar Way
Tucson, AZ -
United States
DUNS: 962538646
HUBZone Owned: No
Woman Owned: No
Socially and Economically Disadvantaged: No
Principal Investigator
 Harry Schmitt
 President
 (520) 306-7639
 haschmitt11@gmail.com
Business Contact
 Harry Schmitt
Title: President
Phone: (520) 306-7639
Email: 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. *

US Flag An Official Website of the United States Government