A Novel and Fast Approach for Scalable Matrix Completion Navy SBIR FY2010.2 Sol No.: Navy SBIR FY2010.2 Topic No.: N102-183 Topic Title: A Novel and Fast Approach for Scalable Matrix Completion Proposal No.: N102-183-0208 Firm: SIGNAL PROCESSING, INC. 13619 Valley Oak Circle ROCKVILLE, Maryland 20850-3563 Contact: Chiman Kwan Phone: (240) 505-2641 Web Site: http://www.signalpro.net 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. Benefits: We expect to produce a real-time system for Navy. We will also integrate our algorithms into some Naval programs. The proposed technology will be very useful for both military and commercial applications. Here we briefly highlight some potential markets where the proposed algorithms will be applicable. Many military (DoD) applications include link recovery in communications, hyperspectral image processing, sensor networks, etc. In addition, Lockheed Martin, Raytheon, GE, MITRE, are also potential customers for this technology. The market for military applications is quite large. We expect the market size will be at 20 million dollars over the next decade. Other potential commercial applications include EEG analysis, internet data mining, machine learning, etc. The size of this market is not small and hard to estimate. We expect the aggregate market size will be similar to that of military applications (20 million over the next decade). Return