Eftychios P.: July 24th

Robust 1-bit compressed sensing and sparse logistic regression: A convex programming approach

Yaniv Plan, Roman Vershynin

(Submitted on 6 Feb 2012 (v1), last revised 19 Jul 2012 (this version, v3))

This paper develops theoretical results regarding noisy 1-bit compressed sensing and sparse binomial regression. We show that a single convex program gives an accurate estimate of the signal, or coefficient vector, for both of these models. We demonstrate that an s-sparse signal in R^n can be accurately estimated from m = O(slog(n/s)) single-bit measurements using a simple convex program. This remains true even if each measurement bit is flipped with probability nearly 1/2. Worst-case (adversarial) noise can also be accounted for, and uniform results that hold for all sparse inputs are derived as well. In the terminology of sparse logistic regression, we show that O(slog(n/s)) Bernoulli trials are sufficient to estimate a coefficient vector in R^n which is approximately s-sparse. Moreover, the same convex program works for virtually all generalized linear models, in which the link function may be unknown. To our knowledge, these are the first results that tie together the theory of sparse logistic regression to 1-bit compressed sensing. Our results apply to general signal structures aside from sparsity; one only needs to know the size of the set K where signals reside. The size is given by the mean width of K, a computable quantity whose square serves as a robust extension of the dimension.

Eftychios P.: Jan. 31st and Feb. 7th

I am planning to lead a very informal discussion on some neat techniques for convex and semidefinite relaxation that can be used to transform intractable optimization problems into approximate but convex ones. I'll also discuss a few applications to statistical neuroscience that we are currently pursuing.

Some background material (although I'm not planning to go over any of these in detail) includes:

http://www.se.cuhk.edu.hk/~manchoso/papers/sdrapp-SPM.pdf
http://arxiv.org/abs/1012.0621
http://www-stat.stanford.edu/~candes/papers/PhaseRetrieval.pdf
http://users.cms.caltech.edu/~jtropp/papers/MT11-Two-Proposals-EJS.pdf

Kolia Sadeghi : Sept. 20

This week, I'll be giving a fly-by overview of a string of recent papers on exact sparse signal recovery that do better than LASSO by solving a sequence of L1 or L2 penalized problems.  Here is a basic narrative:

LASSO uses a penalty weighted by the same lambda for all coefficients.  What happens if you assign different lambdas to each coefficient, and update these lambdas iteratively?  Candes and Boyd do this in Enhancing sparsity by reweighted L1 minimization

You can obtain sparsity by iterative reweighting even for L2-penalized problems: if some of the lambdas become infinite, the corresponding coefficients become exactly zero.  Chartrand and Yin find a particularly good L2 reweighing scheme in Iteratively reweighted algorithms for compressive sensing

All of the above methods reweigh each lambda based only on the value of its corresponding coefficient: they are separable.  In Iterative reweighted l1 and l2 methods for finding sparse solutions, Wipf considers non-separable reweighting schemes that come out of Sparse Bayesian Learning (SBL), which you might also know by the name of Relevance Vector Machine or Automatic Revelance Determination.

Kolia Sadeghi : March 8

At COSYNE, Cadieu and Koepsell had an interesting poster on joint models of amplitude and phase couplings between LFPs of different areas.  There is a paper out on experimental findings [pdf] [supplement], and older papers on estimating models of joint phase couplings [pdf], both of which are interesting.  The model including amplitudes is poster only for now, so I'll go over those papers quickly first.

Fritz Sommer's Adaptive compressive Sensing is good to have seen at least once, so I'll go over it quickly as well if time allows.

Adaptive Compressive Sensing

Fritz Sommer gave a COSYNE 2011 workshop presentation of seemingly magical results coauthored by Guy Isely and Christopher Hillar.

Suppose an area of the brain deals in a signal which is sparse in some underlying unknown dictionary.  This area subsamples the signal with say a random measurement matrix, and sends the subsampled signal to another area.  The receiving area doesn't know what the original signals were, or what the underlying sparsifying dictionary was, or what the measurement matrix were; all it knows are the subsampled measurements it has received.  If the receiving area learns a dictionary in which the subsampled signals it received are sparse, can this sparse representation also be used to linearly represent the original signal?  The answer is yes.

To restore normality and disprove magic, read their NIPS paper.  Apparently a longer paper with proofs is due to come out soon.

Kamiar Rahnama Rad and Chaitu Ekanadham: Nov 10

Chaitu will describe the major results and proofs since the 2005 paper by Candes which gives sufficient conditions for stable recovery of sparse signals from incomplete measurements.  Kamiar will be finishing off where he left off at his last presentation.