Monday, August 25, 2008

CS: SPGL1, SPARCO, CVX news, updated nuclear norm paper, Bayesian NMF, Bregman for Deblurring and another 3D reconstruction from a single image paper.

A new version of the SPGL1 solver (version 1.6) was just released on August 20th, 2008. As gathered from the main page:

In version 1.6, the core SPGL1 function was generalized to solve the above three problems with 1 replaced by any norm . In order to do so, it requires that functions are provided for computing: (1) the (primal) norm , (2) the corresponding dual norm , and (3), the (possibly weighted) Euclidean projection:

project(x):=argminpx2subject top

Using this framework we implemented two new solvers (for more information, see spgdemo.m and Extensions):

Multiple measurement vectors (MMV)

The MMV version of BPDN currently implemented solves

(MMV)minimizeX12subject toAXB22,

where the mixed (pq)-norm, Xpq, (pq1), defined by

Xpq:=imXiTpq1p ,

with X an mn matrix and where Xi denotes the i-th row of X. When weights are given, they apply to each row of X.

Group-sparse BPDN

In group-sparse BPDN each entry of x is assigned a group. Denoting by i the indices of group i, the group-sparse BPDN problem, for 0, is given by:

(Group)minimizeixi2subject toAxb2 .

It is assumed that the i are disjoint and that their union gives the set 1n. When weights are given, they apply to each group.

For more information you may want to check this page. This is a nice addition as we have seen the use of mixed norm popping up several times before and particularly in:
Michael Friedlander, one of the author of SPGL1, further pointed out the following when shown the SPGL1 and TV minimization post by Laurent Jacques:

A while ago I had wondered about extending SPGL1 to other norms, including TV. But I couldn't think of a good way to do projections onto the "TV-norm ball". (Projection onto the one-norm ball is a crucial part of the SPGL1 algorithm.)...The solver now handles "group" one-norms. These are useful when subsets of coefficients need to light up or shut off as a group. Complex-valued problems are a special case, where we expect that the real and complex components should be jointly sparse.

SPARCO is still at version 1.2 but an overview of the Sparco toolbox is given in this technical report.

Way to go Michael and Ewout!

The latest news for CVX ( Matlab Software for Disciplined Convex Programming ) by Michael Grant, Stephen Boyd and Yinyu Ye, are:
Fuller support for 64-bit platforms

CVX version 1.2 now supports 64-bit versions of Matlab on Windows, Linux, and Macintosh platforms; precompiled MEX files are supplied for each of these platforms. Previously, only SDPT3 was supported on 64-bit platforms; now SeDuMi is as well. However, due to the evolution of Matlab's MEX API, Matlab version 7.3 or later is required for 64-bit platforms; and SeDuMi requires version 7.5 or later. (Earlier versions of Matlab are still supported for 32-bit platforms.)

Support for the exponential family of functions

On an unrelated news:


Kayhan said...

Hi Igor,

You may like following videos in ICML'08 about Matrix Factorization:

Bayesian MF:

New approach to solve NMF:

A lot of reading after this post :-)


Igor said...

Hi Kayan,

Thanks for the links.