CS: CS Fall School near Paris, CS BAN, Spatio-Temporal Compressive Sensing and Internet Traffic Matrices

Djalil Chafaï, Olivier Guédon, Guillaume Lecué, Shahar Mendelson and Alain Pajor are organizing a School on Compressed Sensing nearby Paris. From the website:

Fall School Marne-la-Vallée , November 16-20, 2009, on

Compressed sensing - Random matrices - High dimensional geometry

This Fall School will discuss some interactions between compressed sensing, random matrices and high dimensional geometry. It will take place on the campus of Paris-Est Marne-la-Vallée from November 16 to 20, 2009. This school is addressed to non-specialists: participation of postdocs and PhD students is strongly encouraged.

Compressed Sensing is a quite new framework that enables approximate and exact reconstruction of sparse signals from incomplete measurements. It is strongly related to other problems of different fields such as approximation theory (diameter of sections), high dimensional geometry (neighborliness and asymptotic geometry of convex bodies), harmonic analysis (trigonometric diameter and selection of characters) and random matrices (asymptotic behavior of the largest and smallest singular values).

• Gaussian ensembles and universality principles (Djalil Chafaï)
• Empirical methods and selection of characters (Olivier Guédon)
• Basic tools from empirical processes theory applied to the compress sensing problem (Guillaume Lecué)
  
• Applications of chaining methods (Shahar Mendelson)
  
• The Restricted Isometry Property (RIP) of some models of random matrices and High dimensional Geometry (Alain Pajor)
  

The first talk will start on Monday, November 16 at 10:00 and that the last talk will end on Friday, November 20 at 13:30.

You do recall the work mentioned by Pawan Baheti on using Compressive sensing for bio-signal monitoring in what is called Body Area Network (BAN). It is now making some headlines to the Silicon Valley public. I wonder if I should include them in the Compressive Sensing Hardware page (maybe I should since the network of sensor will eventually be different in terms of power and data bandwidth requirements).

What are the odds ? There is another Yin Zhang publishing in the low rank / compressive sensing literature who also lives in Texas. So things become clear, there is:

• Yin Zhang at Rice University in Houston, Texas and 
  
• Yin Zhang at University of Texas in Austin, Texas.
  

Austin and Houston are 166 miles apart.

Here is the Yin Zhang from UT's paper: Spatio-Temporal Compressive Sensing and Internet Traffic Matrices by Yin Zhang, Matthew Roughan, Walter Willinger , Lili Qiu. The abstract reads:

Many basic network engineering tasks (e.g., traffic engineering, capacity planning, anomaly detection) rely heavily on the availabilityand accuracy of traffic matrices. However, in practice it is chal-lenging to reliably measure traffic matrices. Missing values arecommon. This observation brings us into the realm of compressivesensing, a generic technique for dealing with missing values thatexploits the presence of structure and redundancy in many real-world systems. Despite much recent progress made in compressive sensing, existing compressive-sensing solutions often perform poorly for traffic matrix interpolation, because real traffic matrices rarely satisfy the technical conditions required for these solutions.To address this problem, we develop a novel spatio-temporalcompressive sensing framework with two key components: (i) a new technique called SPARSITY REGULARIZED MATRIX FACTORIZATION (SRMF) that leverages the sparse or low-rank nature of real-world traffic matrices and their spatio-temporal properties,and (ii) a mechanism for combining low-rank approximations withlocal interpolation procedures. We illustrate our new framework and demonstrate its superior performance in problems involving interpolation with real traffic matrices where we can successfullyreplace up to 98% of the values. Evaluation in applications suchas network tomography, traffic prediction, and anomaly detection confirms the flexibility and effectiveness of our approach.

From this blog, here are some insight:

· How to fill missing valies in a matrix (could be be a traffic matrix, delay matrix, social proximity matrix)

· They focus on traffic matrices.

· Missing values are quite common – direct measurement in infeasible, measurement unreliable, anomalies appear, and future traffic has not yet appeard

· Many network tasks are sensitive to missing values

· Ideas: 1) Exploit low rank nature of Traffic Matrices (TM); 2) exploit spatio-temporal properties (TM rows and columns close to each other are often close in value); 3) Exploit local strucytures in TMs

· Compressive sensing is used (generic technique for dealing with missing values that exploits the presence of structure and redundancy). However, existing compressive-sensing solutions perform poorly for traffic matrix interpolation.

· In the paper a novel spatio-temporal compressive sensing framework was developed. Key components: 1) a new technique called Sparsity Regularized Matrix Factorization (SRMF) that leverages the low-rank nature of traffic matrices and their spatio-temporal properties; 2) a mechanism for combining low-rank approximations with local interpolation procedures.

· They used real datasets from 3 networks.

· Compared to all other algorithms, this one is always better. Even with 98% missing values, the error is only of about 20%.

Credit: Clair Perry, Charlottetown,Prince Edward Island, Canada, The International Space Station and the Shuttle as photographed from the ground on 9/9/9.