N102-183 TITLE: Scalable Dynamic Matrix Completion for Information Processing and Link Discovery

TECHNOLOGY AREAS: Information Systems, Sensors, Battlespace

RESTRICTION ON PERFORMANCE BY FOREIGN CITIZENS (i.e., those holding non-U.S. Passports): This topic is "ITAR Restricted." The information and materials provided pursuant to or resulting from this topic are restricted under the International Traffic in Arms Regulations (ITAR), 22 CFR Parts 120 - 130, which control the export of defense-related material and services, including the export of sensitive technical data. Foreign Citizens may perform work under an award resulting from this topic only if they hold the "Permanent Resident Card", or are designated as "Protected Individuals" as defined by 8 U.S.C. 1324b(a)(3). If a proposal for this topic contains participation by a foreign citizen who is not in one of the above two categories, the proposal will be rejected.

OBJECTIVE: Develop mathematical, computational, modeling and visualization tools to address the problem of recovering an unknown matrix from a small fraction of its entries. Demonstrate effectiveness of technical approach for (i) Predictive analytics for defense and intelligence communication networks; (ii) Processing of high dimensional sensor data; and (iii) Sensor scheduling.

DESCRIPTION: Matrix completion concerns the problem of recovering an unknown matrix from a small fraction of its entries. It arises in great numbers of important applications and, not surprisingly, has a long history in mathematics. In general, accurate recovery of a matrix from a small number of entries is impossible; but the knowledge that the unknown matrix has low rank radically changes this premise. While solving the matrix completion problem remains of great interest to mathematicians, progress has been incremental. Recent mathematical advances that have arisen from the intensive study of compressive sensing / sampling (CS) are now providing promising new insights [1]. In particular, extensive theoretical and algorithmic studies of signal reconstruction using CS techniques have resulted in the development of rigorous mathematical bounds, a variety of optimization results and computationally efficient algorithms.

Commercial interests currently dominate applied matrix completion research, most famously as a proposed entry for the Netflix prize, and the analysis of internet networks for combating malicious attacks. These predictive analytics problems have close analogs in defense and intelligence communication networks. For example, the intelligence community is keenly interested in link discovery for disrupting incipient, static and evolving terrorist networks. The defense community is concerned with their increasingly vulnerability to the infiltration of communication and sensor networks. Matrix completion mathematics might also be integrated with classes of information theoretic signal processing algorithms which are rapidly moving from a purely academic setting to being evaluated against tactical sensor data. The connection can be seen by noting that a related problem is the distance geometry problem of realizing points in a Euclidean space from a given subset of their pairwise distances [2]. Dynamic matrix completion is a promising new line of research that extends the matrix completion problem to the case where one has the ability to (selectively) fill in a few additional matrix elements to improve the quality of the reconstructed matrix.

PHASE I: Develop mathematical framework and first-generation algorithms for integrating matrix completion methodology with chosen graph-based object detection algorithm (e.g., ISOMAP [3], LLE [4], Laplacian Eigenmaps [5], or Diffusion Maps [6]). Evaluate algorithm performance against sample data set. Propose a plan for the detailed experimental validation of the methodology.

PHASE II: Expand Phase I class of signal processing algorithm to cover anomaly detection, object classification and sensor fusion. Complete and experimentally validate the approach developed in Phase I (expanded to include classification and fusion) by measuring performance against several representative data sets (e.g., a few target classes and two sensor modalities). Develop preliminary mathematical analyses and algorithms to extend the Phase I methodology to include dynamical matrix completion techniques to enable sensor scheduling. Deliver the complete, validated system to ONR.

PHASE III: Commercialization of a validated and verified approach for matrix completion that is scalable and dynamic will enable improved analysis of mobile ad hoc networks. As well, a robust scalable matrix completion algorithm adapted for anomaly detection, object classification and information fusion will find use in a wide range of commercial applications.

PRIVATE SECTOR COMMERCIAL POTENTIAL/DUAL-USE APPLICATIONS: The following industries will benefit from the product developed under this SBIR topic: informatics, data mining, array signal processing, biomedicine, biotechnology, video surveillance, communications devices, networking and management.

REFERENCES:
[1] E. J. Candès and T. Tao, "The power of convex relaxation: Near-optimal matrix completion," submitted for publication, 2009.

[2] A. Singer and M. Cucuringu, "Uniqueness of Low-Rank Matrix Completion by Rigidity Theory," submitted for publication, 2009.

[3] J. B. Tenenbaum, V. de Silva, and J. C. Langford, "A Global Geometric Framework for Nonlinear
102:7432-7437 imensionality Reduction," Science, pp. 2319-2323, 2000.

[4] S. T. Roweis, et al., Nonlinear Dimensionality Reduction by Locally Linear Embedding, Science, pp. 2323-2326, 2000.

[5] M. Belkin, and P. Niyogi, "Laplacian Eigenmaps for Dimensionality Reduction and Data Representation," Neural Computation, Vol. 15, 6, pp. 1373-1396, 2003.

[6] R. R. Coifman, S. Lafon, A. B. Lee, M. Maggioni, B. Nadler, F. Warner, and S. W. Zucker, "Geometric diffusions as a tool for harmonic analysis and structure definition of data: Multiscale methods," PNAS, 102, 7432-7437 2005.

[7] J. Wright, A. Ganesh, S. rao, Y. Ma, "Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Matrices via Convex Optimization", submitted for publication, 2009.

KEYWORDS: Graph Processing; Data Adaptive Processing; Information Assurance; Information Operations.

** TOPIC AUTHOR (TPOC) **

DoD Notice:   Between April 21 and May 19, 2010, you may talk directly with the Topic Authors to ask technical questions about the topics. For reasons of competitive fairness, direct communication between proposers and topic authors is not allowed starting May 19, 2010, when DoD begins accepting proposals for this solicitation.

However, proposers may still submit written questions about solicitation topics through the DoD's SBIR/STTR Interactive Topic Information System (SITIS), in which the questioner and respondent remain anonymous and all questions and answers are posted electronically for general viewing until the solicitation closes. All proposers are advised to monitor SITIS (10.2 Q&A) during the solicitation period for questions and answers, and other significant information, relevant to the SBIR 10.2 topic under which they are proposing.

If you have general questions about DoD SBIR program, please contact the DoD SBIR Help Desk at (866) 724-7457 or email weblink.