CS: A Unified Approach for Minimizing Composite Norms and more.

We started the week with a preprint that expands the study of the Donoho-Tanner phase transition to the noisy case for l_1 recovery. Today, we close the week with another work expanding the recent work on Stable Principal Component Pursuit by Zihan Zhou, Xiaodong Li, John Wright, Emmanuel Candes, and Yi Ma. I found it a little bit by accident as my arxiv search did not find it. It is: A Unified Approach for Minimizing Composite Norms by Necdet Serhat Aybat and Garud Iyengar. The abstract reads:

We propose a first-order augmented Lagrangian algorithm (FALC) that solves min{mu1|X|_* + mu2 |C(X)-d|_1 : A(X)=b}, where C(.) and A(.) denote linear operators from Re^{m*n} to a vector space. FALC solves this semidefinite problem by inexactly solving a sequence of problems of the form min{lambda(k)(mu1 |X|_* + mu2 |s|_1)+|A(X)-b-lambda(k)theta1(k)|_2^2+|C(X)+s-d-lambda(k)theta2(k)|_2^2}, for an appropriately chosen sequence of multipliers {lambda(k),theta1(k),theta2(k)}. Each of these subproblems are solved using Algorithm 3 in [31] by Paul Tseng wherein each update can be computed using singular value decomposition (SVD). We show that FALC converges to the optimal solution X* of the composite norm minimization problem if the optimal solution is unique. We also show that there exists a priori fixed sequence {lambda(k)} such that for all epsilon>0, iterates X(k) computed by FALC are epsilon-feasible and epsilon-optimal after O(1/epsilon) iterations, where the complexity of each iteration is O(min{n*m^2,m*n^2}). We also show that FALC can be extended very simply to solve more general problems of the form: min{mu1 |X|_{alpha}+ mu2 |C(X)-d|_{beta} + : A(X)=b, Q-F(X) is psd, |G(X)-h|_{gamma} <= rho}, where the matrix norm |X|_{alpha} denotes either the Frobenius, the nuclear, or the L_2-operator norm, the vector norms |C(X)-d|_{beta}, and |G(X) - h|_{gamma} denote either the L2-norm, L1-norm or the L{infty}-norm, and A(X), C(X), G(X) and F(X) are linear operators from Re^{m*n} to vector spaces of appropriate dimensions and psd is the set of positive semidefinite matrices. All the convergence properties of FALC continue to hold for this more general problem.

Garud Iyengar lets me know that FALC should be available at some point in the future.

In this blog entry entitled Sony Shrinks CCD Pixel to 1.43um, one can see how Sony is making its pixels smaller: by adding a lens!
In another entry entitled Aptina Explains its BSI-FSI Strategy, Announces New Sensors one can see how the requirements for video and stills are eventually diverging.

While those information are not strictly related to CS, I believe they are good rules of thumbs for trying to design "exotic" systems.

In another direction, Andy Stove at Thales will give a talk entitled: Compressive sampling of radar and electronic warfare data on Friday June 4th at 10:00 Industrial and Interdisciplinary Workshops DH 1st floor SR at the University of Oxford. The abstract of the talk reads:

'Compressive sampling' is a topic of current interest. It relies on data being sparse in some domain, which allows what is apparently 'sub Nyquist' sampling so that the quantities of data which must be handled become more closely related to the information rate. This principal would appear to have (at least) three applications for radar and electronic warfare:
The most modest application is to reduce the amount of data which we must handle: radar and electronic warfare receivers generate vast amounts of data (up to 1Gbit/second or even 10Gbit.sec). It is desirable to be able to store this data for future analysis and it is also becoming increasingly important to be able to share it between different sensors, which, prima facie, requires vast communication bandwidths and it would be valuable to be able to find ways to handle this more efficiently.
The second advantage is that if suitable data domains can be identified, it may also be possible to pre-process the data before the analogue to digital converters in the receivers, to reduce the demands on these critical components.
The most ambitious use of compressive sensing would be to find ways of modifying the radar waveforms, and the electronic warfare receiver sampling strategies, to change the domain in which the information is represented to reduce the data rates at the receiver 'front ends', i.e. make the data at the front end better match the information we really want to acquire.
The aim of the presentation will be to describe the issues with which we are faced, and to discuss how compressive sampling might be able to help. A particular issue which will be raised is how we might find domains in which the data is sparse.