Scientists and Engineers often struggle to deduce the state or structure of a system from partial, noisy measurements. The corresponding problems are ill-posed because there are fewer measurements available than the number of parameters they would like to estimate. In practice, however, many interesting signals or models contain considerably fewer degrees than the apparent number of parameters: a small number of genes may constitute the signature of a disease, very few parameters may specify the correlation structure of a time series, or a sparse collection of geometric constraints may determine a molecular configuration. Discovering, leveraging, or recognizing such low-dimensional structure plays an important role in posing inverse problems well.
This project pursues a unified approach to transform notions of simplicity and latent low-dimensionality into convex penalty functions. The investigators focus on a theoretically sound suite of data analysis algorithms designed to decompose complex signals into sums of a small number of simple atoms. The work first catalogs the objects and structures that can be recovered from a small number of measurements using atomic decomposition algorithms, in order to show that many structures of significant scientific and technological interest need only be probed a few times to extract complete and accurate knowledge. Second, the project explores a range of practically useful implementations of atomic decomposition algorithms for data recovery, enabling efficient solutions of large-scale problems with guaranteed success. Finally, practical implementation in a diverse set of applications, including web-scale data analysis, high-throughput biology, and experimental physics, continually motivate and refine this mathematical research program.
