USA flag logo/image

An Official Website of the United States Government

Mathematical and Computational Framework for Matrix Completion with Nonuniform…

Award Information

Agency:
Department of Defense 		Branch:
N/A 		Award ID:
 Program Year/Program:
2011 / SBIR
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 -
View profile »
Woman-Owned: No
Minority-Owned: No
HUBZone-Owned: No
 
Phase 1
Fiscal Year: 2011
Title: Mathematical and Computational Framework for Matrix Completion with Nonuniform Sampling in Resource Constrained Environments
Agency: DOD
Contract: N00014-11-M-0478
Award Amount: $69,748.00
 

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.

Principal Investigator:

Harry Schmitt
President
(520) 306-7639
haschmitt11@gmail.com

Business Contact:

Harry Schmitt
President
(520) 306-7639
haschmitt11@gmail.com
Small Business Information at Submission:

PhyLas
8637 East Dunbar Way Tucson, AZ -

EIN/Tax ID: 272330946
DUNS: N/A
Number of Employees:
Woman-Owned: No
Minority-Owned: No
HUBZone-Owned: No