In many engineering applications, notions of complexity, order or dimension of a model can be expressed by the rank of a matrix, while prior information and model accuracy often correspond to convex constraints on this matrix. Parsimonious Modeling involves the computational problem of minimizing matrix rank subject to convex constraints. Examples include problems in system identification, model reduction, and Euclidean embedding, arising in control, signal processing, and machine learning. The rank minimization problem is known to be computationally intractable in general. The work is inspired by the recently developed framework of compressed sensing for sparse signals. A preliminary work by the PI and her collaborators, points to a rich generalization of this theory from sparse vectors to low-rank matrices, showing that some classes of this hard problem can be solved efficiently.
The proposed research builds on advances in compressed sensing and its underlying math, as well as convex optimization. The program has three thrusts: (1) theoretical characterization of classes of rank minimization problems that can be solved efficiently, (2) development of efficient semidefinite programming algorithms for this problem, (3) a focus on applications of rank minimization (e.g., in system identification). This program combines practical impact with conceptual depth, unifying existing notions of parsimony (such as vector sparsity and matrix rank) as well as the computational methods to address them.
Broader impact:
This program will leverage extensive collaborations between pure mathematicians and engineers, and should motivate research in mathematics in areas not traditionally considered ?applied". Results and computational tools developed can be used by researchers in various application fields. Research from this project will be integrated with the PI's past work into a new project-driven graduate course at UW. Students at all levels will be engaged. A workshop and a mathematical problem solving competition is planned as part of UW's BRIDGE program for incoming women and minority freshman.
