Monday, April 15, 2013

Compressive System Identification (CSI): Theory and Applications of Exploiting Sparsity in the Analysis of High-Dimensional Dynamical Systems

Borhan Sanandaji sent me the following (a compilation of two emails since I did not have time to show the first one a month ago):

Hi Igor,

I hope everything goes well with you. I would like to bring your and Nuit Blanche Reader's attention to my PhD Thesis and Defense Presentation Slides which can be found on mywebpage. In my PhD thesis ``Compressive System Identification (CSI): Theory and Applications of Exploiting Sparsity in the Analysis of High-Dimensional Dynamical Systems,'' I tried to combine the tools and ideas in Compressive Sensing and Sparse Signal Processing with Control Theory when dynamical systems are involved and in applications such as observability of linear systems whose initial state is sparse, identification of systems with sparse representations (impulse response, ARX, etc.), and topology identification of large-scale interconnected dynamical systems with sparse flow.....
I [also] would like to bring your attention to a couple of our papers which both have a review/tutorial flavor. The first paper A Review of Sufficient Conditions for Structure Identification in Interconnected Systems reviews some of the recent results on Compressive Topology Identification (CTI) of large-scale but sparse-flow interconnected dynamical systems with a particular focus on sufficient recovery conditions. In the second paper A Tutorial on Recovery Conditions for Compressive System Identification of Sparse Channels we review some of the recent results concerning Compressive System Identification (CSI) (identification from few measurements) of sparse channels (and in general, Finite Impulse Response (FIR) systems) when it is known a priori that the impulse response of the system under study is sparse (high-dimensional but with few nonzero entries) in an appropriate basis. As a quick note, our Concentration of Measure Inequalities for Compressive Toeplitz Matrices with Applications is now published in the IEEE TSP (See also the companion technical report). 
Once again, I would like to thank you for providing the Nuit Blanche which has been a useful source on CS over my PhD studies.


Thanks Borhan !

Here is Borhan 's thesis: Compressive System Identification (CSI): Theory and Applications of Exploiting Sparsity in the Analysis of High-Dimensional Dynamical Systems. The abstract reads:
The information content of many phenomena of practical interest is often much less thanwhat is suggested by their actual size. As an inspiring example, one active research area inbiology is to understand the relations between the genes. While the number of genes in aso-called gene network can be large, the number of contributing genes to each given genein the network is usually small compared to the size of the network. In other words, thebehavior of each gene can be expressed as a sparse combination of other genes.The purpose of this thesis is to develop new theory and algorithms for exploiting thistype of simplicity in the analysis of high-dimensional dynamical systems with a particu-lar focus on system identi cation and estimation. In particular, we consider systems witha high-dimensional but sparse impulse response, large-scale interconnected dynamical sys-tems when the associated graph has a sparse ow, linear time-varying systems with fewpiecewise-constant parameter changes, and systems with a high-dimensional but sparse ini-tial state. We categorize all of these problems under the common theme of CompressiveSystem Identi cation (CSI) in which one aims at identifying some facts (e.g., the impulseresponse of the system, the underlying topology of the interconnected graph, or the initialstate of the system) about the system under study from the smallest possible number ofobservations.Our work is inspired by the eld of Compressive Sensing (CS) which is a recent paradigmin signal processing for sparse signal recovery. The CS recovery problem states that a sparsesignal can be recovered from a small number of random linear measurements. Compared tothe standard CS setup, however, we deal with structured sparse signals (e.g., block-sparsesignals) and structured measurement matrices (e.g., Toeplitz matrices) where the structureis implied by the system under study

A Review of Sufficient Conditions for Structure Identification in Interconnected Systems by Borhan Sanandaji   Tyrone L. Vincent  Michael B. Wakin
Abstract: Structure identi fication of large-scale but sparse-flow interconnected dynamical systems from limited data has recently gained much attention in the control and signal processing communities. This paper reviews some of the recent results on Compressive Topology Identifi cation (CTI) of such systems with a particular focus on su fficient recovery conditions. We list and discuss the key elements that influence the recovery performance of CTI, namely, the network topology, the number of measurements, and the input sequence. In regards to the last element, we analyze the recovery conditions with respect to an experiment design.

We derive Concentration of Measure (CoM) inequalities for randomized Toeplitz matrices. Theseinequalities show that the norm of a high-dimensional signal mapped by a Toeplitz matrix to a lowdimensional space concentrates around its mean with a tail probability bound that decays exponentiallyin the dimension of the range space divided by a quantity which is a function of the signal. For theclass of sparse signals, the introduced quantity is bounded by the sparsity level of the signal. However,we observe that this bound is highly pessimistic for most sparse signals and we show that if a random distribution is imposed on the non-zero entries of the signal, the typical value of the quantity is boundedby a term that scales logarithmically in the ambient dimension. As an application of the CoM inequalities,we consider Compressive Binary Detection (CBD).

Why is this work important ?

As I mentioned earlier, there is an extreme paucity of tools for blind deconvolution of biochemical networks, Making sense of these networks is clearly key to solving many problems in medical research and potentially synthetic biology. In short, beyond devising the right sensors such as MRI, CT scanners and others, performing these inverse problems i,e, network identification on graphs is clearly a tremendous tool for potentially curing living things  [1,2] and building a better future. 

[1] Reverse Engineering Biochemical Networks and Compressive Sensing, It's quite simply, the stuff of Life...
[2] Instances of Null Spaces: Can Compressive Sensing Help Study Non Steady State Metabolic Networks ?.

Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

No comments: