USA flag logo/image

An Official Website of the United States Government

A Novel and Fast Approach for Scalable Matrix Completion

Award Information

Agency:
Department of Defense
Branch:
N/A
Award ID:
Program Year/Program:
2011 / SBIR
Agency Tracking Number:
N102-183-0208
Solicitation Year:
2010
Solicitation Topic Code:
N102-183
Solicitation Number:
2010.2
Small Business Information
SIGNAL PROCESSING, INC.
9700 Great Seneca Highway Rockville, MD -
View profile »
Woman-Owned: No
Minority-Owned: No
HUBZone-Owned: No
 
Phase 1
Fiscal Year: 2011
Title: A Novel and Fast Approach for Scalable Matrix Completion
Agency: DOD
Contract: N00014-10-M-0479
Award Amount: $99,998.00
 

Abstract:

Matrix completion has many applications such as link recovery, data mining, image reconstruction, etc. We propose a novel algorithm to solve the above mentioned matrix completion problem. In particular, we have derived a novel framework to approximate the rank by another function. This novel framework not only leads to state of the art results in reconstructing missing entries in data matrices, it also can be generalized to find missing values in tensor data which is considered to be significantly harder than the matrix case due to the complexity in its structure and which are unable to solve by previous approaches. Moreover, our new framework can easily deal with noisy measurements. We have proven two theorems to provide theoretical guarantees for convergence of solutions. Finally, we also have efficient implementation of our framework. Preliminary comparative studies with several recent algorithms in matrix completion have demonstrated that our algorithm achieves comparable approximation performance of the best algorithm in the literature and yet only requires 1% of the computations. The matrix dimension was several thousands. This means our algorithm is suitable for real-time matrix and tensor completion of large scale applications.

Principal Investigator:

Chiman Kwan
Chief Technology Officer
(240) 505-2641
chiman.kwan@signalpro.net

Business Contact:

Chihwa Yung
Chief Operations Officer
(301) 315-2322
chihwa.yung@signalpro.net
Small Business Information at Submission:

SIGNAL PROCESSING, INC.
13619 Valley Oak Circle ROCKVILLE, MD -

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