## Wednesday, January 05, 2011

### CS; In-situ Imaging, Sparse recovery with unknown variance: a LASSO-type approach, Wireless Peer-to-Peer Mutual Broadcast via Sparse Recovery

As I was re-reading last year's entry, I was reminded of this in-situ imaging presentation entitled:  Passive sensor imaging using cross correlations of ambient noise signals by Josselin Garnier

newer papers on the same subject have since surfaced:
Using scattering in a medium to get better resolution, I like it and I wonder how this fits into studies like the In Situ Compressive Sensing  by Lawrence Carin, Dehong Liu and Bin Guo.

In other news, from arxiv we have two new papers:

We address the issue of estimating the regression vector $\beta$ and the variance $\sg^{2}$ in the generic s-sparse linear model $y = X\beta+z$, with $\beta\in\R^{p}$, $y\in\R^{n}$, $z\sim\mathcal N(0,\sg^2 I)$ and $p> n$. We propose a new LASSO-type method that jointly estimates $\beta$, $\sg^{2}$ and the relaxation parameter $\lb$ by imposing an explicit trade-off constraint between the $\log$-likelihood and $\ell_1$-penalization terms. We prove that exact recovery of the support and sign pattern of $\beta$ holds with probability at least $1-O(p^{-\alpha})$. Our assumptions, parametrized by $\alpha$, are similar to the ones proposed in \cite{CandesPlan:AnnStat09} for $\sg^{2}$ known. The proof relies on a tail decoupling argument with explicit constants and a recent version of the Non-Commutative Bernstein inequality \cite{Tropp:ArXiv10}. Our result is then derived from the optimality conditions for the estimators of $\beta$ and $\lb$. Finally, a thorough analysis of the standard LASSO estimator as a function of $\lb$ allows us to construct an efficient Newton scheme for the fast computation of our estimators.
and
Wireless Peer-to-Peer Mutual Broadcast via Sparse Recovery by Lei Zhang, Dongning Guo. The abstract reads:
Consider a problem frequently seen in wireless peer-to-peer networks: Every node has messages to broadcast to its peers, namely, all nodes within one hop. Conventional schemes allow only one transmission to succeed at a time in a two-hop neighborhood, because 1) simultaneous transmissions in the neighborhood collide, and 2) affordable radio is half-duplex and cannot simultaneously transmit and receive useful signals. In this paper, we propose a novel solution for the peer-to-peer mutual broadcast problem, which exploits the multiaccess nature of the wireless medium and addresses the half-duplex constraint at the fundamental level. The defining feature of the scheme is to let all nodes send their messages at the same time, where each node broadcasts a codeword (selected from its unique codebook) consisting of on-slots and off-slots, where it transmits only during its on-slots, and listens to its peers through its own off-slots. Each node decodes the messages of its peers based on the received superposed signals through its own off-slots. Decoding can be viewed as a problem of sparse support recovery based on linear measurements (with erasures). In case each message consists of a small number of bits, an iterative message-passing algorithm based on belief propagation is developed, the performance of which is characterized using a state evolution formula in the limit where each node has a large number of peers. Numerical results demonstrate that the message-passing algorithm outperforms popular compressed sensing algorithms such as CoSaMP and AMP. Furthermore, to achieve the same reliability for peer-to-peer broadcast, the proposed scheme achieves three to five times the rate of ALOHA and carrier-sensing multiple-access (CSMA) in typical scenarios.