Current events

From FazelWiki

1 Compressed sensing Reading group
2 Visitor: Venkat Chandrasekaran, MIT, May 18-21, 2009
3 Visitor: Ben Recht, Caltech, Nov 18-19, 2008
4 EE591: RCM Seminar Series: Topics in Optimization with Engineering Applications
5 List of Speakers

Compressed sensing Reading group

We are interested in compressed sensing, in particular its mathematical foundation, and related problems where concepts from this topic can be extended to. We held weekly meetings in spring 2009 (list of papers discussed can be found below).

The meetings will be continued in summer 2009. In the first meeting there'll be a brief review of the main concepts for those who missed the meetings in spring.

MEETING TIME/PLACE: Tuesdays, 3pm, location: EE 403

LIST OF PAPERS:

Papers discussed in spring 2009:

Introduction to CS: http://www-dsp.rice.edu/files/cs/CSintro.pdf

RIP (restricted isometry) and exact recoverability of sparse vectors: http://www.acm.caltech.edu/~emmanuel/papers/RIP.pdf

Random matrices and recoverability with high probability: http://dsp.rice.edu/files/cs/JL_RIP.pdf

The matrix case: exact recovery of low-rank matrices: http://faculty.washington.edu/mfazel/low-rank-v2.pdf

Finding sparse+low-rank matrix decompositions: http://ssg.mit.edu/~venkatc/cspw_slr_sysid09.pdf

Papers for summer 2009:

Week 1--Tues June 30: Derivation of compressed sensing results using simple null-space properties:

We discussed this note by Stephen Vavasis (from his course at the Univ of Waterloo: http://www.student.math.uwaterloo.ca/~co769/) which proves the uniqueness, exact recovery, and stable recovery of sparse vectors from Ax=b, if A's nullspace has a certain property (called the `spherical section property'):

http://www.student.math.uwaterloo.ca/~co769/simplif.pdf

Week 2--Tues July 7: We'll continue our discussion with a second note by Stephen Vavasis, which proves the `spherical section property' for random matrices:

http://www.student.math.uwaterloo.ca/~co769/spher2.pdf

Week 3--Tues July 14:

the Matrix Completion problem: http://www.acm.caltech.edu/~emmanuel/papers/NoisyCompletion.pdf

Week 4--Tues July 21:

We'll finish the paper from Week 3.

Week 5--Tues July 28:

This week we'll discuss a paper on algorithms for nuclear norm minimization. Ting-Kei Pong (UW math dept) will present this paper:

http://www.columbia.edu/~sm2756/FPCA_Matrix_Rank_MathProg_revised.pdf

Week 6--Tues Aug 3:

Sharp thresholds for noisy/high-dimensional recovery of sparsity:

http://www.eecs.berkeley.edu/~wainwrig/Papers/Wai_SharpThresh.pdf

Week 7--Tues Aug 10:

Prof. Marina Meila (UW statistics dept) will be giving us an overview of her recent work in " Gravimetric detection by compressed sensing".

Week 8--Tues Aug 17:

Information-theoretic lower bounds on sparse recovery under noise:

http://www.stat.berkeley.edu/tech-reports/725.pdf

There will be no meetings in September. We will resume the readings in October, stay tuned!

Below are a few other suggested papers. Feel free to suggest a paper you'd like to present. Topics and order will be discussed in the meetings, feedback from regular participants is welcome:

Another approach to null-space based analysis:

http://www.caam.rice.edu/~zhang/reports/tr0811.pdf

Matrix rank minimization problems:

Low-rank matrix recovery under RIP: http://faculty.washington.edu/mfazel/low-rank-v2.pdf

Another approach to matrix completion: http://www.stanford.edu/~montanar/PAPERS/FILEPAP/approx_fin.pdf

Sparse graphical model structure recovery:

http://www.eecs.berkeley.edu/~wainwrig/Papers/RavWaiLaf.pdf

The Dantzig selector:

http://www.acm.caltech.edu/~emmanuel/papers/DantzigSelector.pdf

Compressed learning: http://dsp.rice.edu/files/cs/cl.pdf

Learning compressed sensing: http://www.cs.huji.ac.il/~yweiss/allerton-final.pdf

[edit]

Visitor: Venkat Chandrasekaran, MIT, May 18-21, 2009

Venkat Chandrasekaran from MIT will be visiting and giving a talk in our next Compressed Sensing Reading Group meeting. More information below.

click here for Venkat's visit schedule

Thursday May 21, 2009, 4:45-6pm

EE Bldg, 403

TITLE: Rank-Sparsity Incoherence for Matrix Decomposition

ABSTRACT: Complex systems and models arise in a variety of problems in science and engineering. In many applications such complex systems and models are often composed of multiple simpler systems and models. In order to better understand the behavior and properties of a complex system, a natural approach is to decompose the system into its simpler components.

We consider one such situation in which a complex system represented by a matrix is formed adding an unknown sparse matrix to an unknown low-rank matrix. Our goal is to decompose the given matrix into its sparse and low-rank components. Such a problem arises in a number of applications in computational complexity, statistical model selection, and system identification. However, obtaining an exact solution is NP-hard in general. We propose a convex optimization formulation to splitting the specified matrix into its components; in fact our approach reduces to solving a semidefinite program. We develop a notion of rank-sparsity incoherence - an uncertainty principle between the sparsity patterns of matrices and their row/column spaces - to characterize both fundamental identifibility as well as (deterministic) sufficient conditions for exact recovery using our method. We conclude with some implications of our analysis for problems in computer science such as those involving matrix rigidity. Our approach also provides a global alternative to local methods such as the EM algorithm for statistical model selection with latent variables.

BIO: Venkat Chandrasekaran received the B.S. degree in electrical engineering, the B.A. degree in mathematics from Rice University, Houston, TX, in 2005, and the S.M. degree in electrical engineering from the Massachusetts Institute of Technology, Cambridge, in 2007, where he is currently working towards the Ph.D. degree with the Stochastic Systems Group. His research interests include statistical signal processing, machine learning, convex optimization, and computational harmonic analysis.

[edit]

Visitor: Ben Recht, Caltech, Nov 18-19, 2008

Dr. Ben Recht from Center for Mathematics of Information, Caltech, will be visiting UW EE/CSE on Nov 18th, and giving a talk in the CS theory seminar. More information below.

click here for Ben Recht's visit schedule

Tuesday Nov 18, 2008, 1:30-2:20pm

CSE 503 (Paul Allen Center)

TITLE: Pulling Rank: Inference from Incomplete Data

ABSTRACT: How can we infer answers from a survey that is only partially filled out? Suppose we ask a large collection of individuals a series of questions. We collect some data but, unfortunately, many questions are left unanswered. Is it possible for us to make an educated guess about what the missing answers should be? How can we make such a guess? In general, with no additional assumptions, this is impossible. However, if we assume that we can arrange all of the answers into a low rank matrix, there is often a unique assignment for the missing entries.

In this talk, I will discuss very general settings in which one can perfectly recover all of the missing entries of a low-rank matrix from a sufficiently large random subset of entries by solving a convex programming problem. Out of all of the matrices whose entries agree with the given subset, this program finds the matrix with the minimum nuclear norm (also known as the Ky-Fan norm or the Schatten 1-norm). I will show that if the number of sampled entries is greater than C n^{1.25} r log n for some positive numerical constant C, then with very high probability, most n x n matrices of rank r are perfectly recovered by the nuclear norm heuristic. The techniques for proving the main results build upon geometric ideas from the the recent literature on "Compressed Sensing" together with probabilistic tools such as the powerful techniques of Bourgain and of Rudelson for bounding norms of operators between Banach spaces. These results illustrate a general program for perfectly reconstructing geometric objects from very limited information.

BIOGRAPHY:

Benjamin Recht is a senior postdoctoral fellow at Center for the Mathematics of Information---a multidisciplinary research center established to promote information science and technology at Caltech. His research focuses on scalable computational tools based on convex optimization and randomized algorithms for large-scale data analysis, system identification, machine learning, and mathematical physiology. Benjamin received his B.S. with honors in Mathematics from the University of Chicago in 2000, and received a M.S. in 2002 and PhD in 2006 from the MIT Media Laboratory.

[edit]

EE591: RCM Seminar Series: Topics in Optimization with Engineering Applications

Spring quarter 2008

Time: Fridays 2:30-3:30pm

Location: EE 105

Organizers: Maryam Fazel, and Mehran Mesbahi

Can be taken as course EE/AA/ME/ChemE 591: RCM seminar, for 1 unit credit. To get credit, no more than 2 talks can be missed.

A related seminar series: Math department's Optimization Seminar, organized by Professor Jim Burke. Here is the link

Reading group: (optional) We'll meet most Thursday evenings to discuss recommended papers by the speaker that week. Details below. Everyone Welcome!

[edit]