[talks] S Jafarpour general exam

[Melissa Lawson]

Sina Jafarpour will present his research seminar/general exam on Friday January 16
at 2:30 PM in Room 402.  The members of his committee are:  Rob Calderbank (advisor), 
Rob Schapire, and Andrea LaPaugh.  Everyone is invited to attend his talk, and those 
faculty wishing to remain for the oral exam following are welcome to do so.  His 
abstract and reading list follow below.
------------------------------------------- 

The magic of sparsity.

Joint work with Robert Calderbank, Robert Schapire, and Ingrid Daubechies.

Compressed Sensing is a novel data acquisition method suitable when either the measurement
or the compression is costly. The traditional approach to compressed sensing uses convex
optimization methods, which are based on some "near isometry" property of the sensing
matrix. This approach is costly in terms of the recovery time as well as the required
storage.

In this talk, we present two new efficient sensing methods. We first show how expander
graphs are appropriate for compressed sensing in terms of providing explicit and efficient
sensing matrices as well as a simple and efficient recovery algorithm. Our second result
provides efficient deterministic sensing. We show very simple conditions a matrix should
satisfy in order to satisfy statistical restricted isometry property. This leads to
deterministic sensing matrices in which the recovery time only depends on the number of
measurements and might even bypass the random sensing lower bounds..

Finally, we show how compressed sensing can be regarded as a universal sparse
dimensionality reduction technique. Especially, we provide tight bounds, demonstrating
that the soft-margin SVM classifier in compressed domain is almost as accurate as the best
classifier in high dimension. This is beneficial in the compressed sensing point of view
by reducing the recovery time, and also in the machine learning point of view by bypassing
the curse of dimensionality.



Books:
======
 
1. S. Russell and P. Norvig. Artificial Intelligence: A modern approach. 
   Chapters: 
     3.1-3.5
     4.1-4.3
     6
     7.1-7.6
     11.1, 11.5
     8.1-8.3
     13.1-13.6
     14.1-14.5
     15.1-15.6
     16.1-16.3
     17.1-17.4
     18.1-18.5
     20.1-20.3,20.5-20.6
     21.1-21.4

2. Lecture notes of Computer Science 511: Theoretical Machine learning, by Robert
Schapire, spring 2008.

3. S. Boucheron1, O. Bousquet and G. Lugosi, Theory of classification, a survey of some
recent advances, ESAIM: Probability and Statistics 9, 323 - 375, 2005.
http://www.econ.upf.edu/~lugosi/esaimsurvey.pdf


4. S. Boyd and L. Vandenberghe, Convex Optimization.
   Chapters:
     2.1-2.3
     3.1.1-3.2
     4.1-4.4
     5.1-5.2
     5.4-5.5


Papers:
=======
 
1. C. Burges. A tutorial on Support Vector Machines for pattern recognition. Data Mining
and Knowledge Discovery, 2(2):955-974, 1998.
http://www.umiacs.umd.edu/~joseph/support-vector-machines4.pdf

2. S. Shalev-Shwartz and N. Srebro. SVM Optimization: Inverse Dependence on Training set
size. ICML, 2008. http://icml2008.cs.helsinki.fi/papers/266.pdf

3. A. Blum. Random Projection, Margins, Kernels, and Feature-Selection. LNCS vol 3940, pp.
52--68, 2006. www.cs.cmu.edu/~avrim/Papers/randomproj.pdf 

4. R. Schapire and Y. Singer. Improved boosting algorithms using confidence-rated
predictions. Machine Learning, 37(3):297-336, 1999.
http://www.cs.princeton.edu/~schapire/uncompress-papers.cgi/SchapireSi98.ps

5. R. Baraniuk, Compressive sensing. IEEE Signal Processing Magazine, 24(4), pp. 118-121,
July 2007 http://www.dsp.ece.rice.edu/cs/baraniukCSlecture07.pdf

6. E. Candès and M. Wakin, An introduction to compressive sampling. IEEE Signal Processing
Magazine, 25(2), pp. 21 - 30, March 2008. http://www.dsp.ece.rice.edu/cs/CSintro.pdf


7. R. Berinde and P. Indyk, Sparse recovery using sparse random matrices. Preprint, 2008.
http://people.csail.mit.edu/indyk/report.pdf

8. R. Baraniuk, M. Davenport, R. DeVore, and M. Wakin, A simple proof of the restricted
isometry property for random matrices using Johnson-Lindenstrauss Lemma. To appear in
Constructive Approximation. http://www.dsp.ece.rice.edu/cs/JL_RIP.pdf


9. V. Chandar, A negative result concerning explicit matrices with the restricted isometry
property. Preprint, 2008 http://www.dsp.ece.rice.edu/cs/Venkat_CS.pdf

10. L. Applebaum, S. Howard, S. Searle, and R. Calderbank, Chirp sensing codes:
Deterministic compressed sensing measurements for fast recovery. Applied and Computational
Harmonic Analysis, September 2008. http://www.dsp.ece.rice.edu/cs/chirpCode.pdf

11.S. D. Howard, A. R. Calderbank, and S. J. Searle, A fast reconstruction algorithm for
deterministic compressive sensing using second order Reed-Muller codes. (Conf. on Info.
Sciences and Systems (CISS), Princeton, New Jersey, March 2008)
http://www.dsp.ece.rice.edu/cs/HCS_CISS_2008.pdf

12.W. Xu and B. Hassibi, Efficient compressive sensing with deterministic guarantees using
expander graphs. http://www.dsp.ece.rice.edu/cs/cs-expander2.pdf