SITIS Archives - Topic Details
Program:  SBIR
Topic Num:  N102-183 (Navy)
Title:  Scalable Dynamic Matrix Completion for Information Processing and Link Discovery
Research & Technical Areas:  Information Systems, Sensors, Battlespace

Acquisition Program:  
 RESTRICTION ON PERFORMANCE BY FOREIGN NATIONALS: 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 nationals 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 national who is not in one of the above two categories, the proposal may 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.

Questions and Answers:
Q: Are there some sample data sets of interest to the Navy be made publicly available?
A: Yes, Navy-related datasets will be available for testing and validation in Phase II.
Q: For Phase I testing and demo, do we generate a sample data set ourselves, or will the Navy also supply that also?
A: You may use your dataset for algorithm development in Phase I.
Q: Phase I requirement is about integrating matrix completion methodology in graph based algorithms like Laplacian eigenmaps. Is it a correct understanding that we are requested to generalize the matrix completion algorithms to graph based algorithms like Laplacian eigenmaps?
A: No, we are not seeking generalization of the matrix completion problem to graphs.

Record: of