Matrix Factorization This Week.

First, we start today with a different approach to computing most nuclear norm minimization and other convex optimization problems with Convex Optimization without Projection Steps by Martin Jaggi. The abstract reads:

We study the general problem of minimizing a convex function over a compact convex domain. We will investigate a simple iterative approximation algorithm that does not need projection steps in order to stay inside the optimization domain. Instead of a projection step, the linearized problem defined by a current subgradient is solved, which gives a step direction that will naturally stay in the domain. The approach generalizes the sparse greedy algorithm of Clarkson (and the low-rank SDP solver by Hazan) to arbitrary convex domains, and to using subgradients for the case of non-differentiable convex functions. Analogously, we give a convergence proof guaranteeing {\epsilon}-small duality gap after O(1/{\epsilon}) iterations. The framework allows us understand the sparsity of approximate solutions for any l1-regularized convex optimization problem, expressed as a function of the approximation quality. We obtain matching upper and lower bounds of {\Theta}(1/{\epsilon}) for the sparsity for l1-problems. The same bounds apply to low-rank optimization with bounded trace, showing that rank O(1/{\epsilon}) is best possible here as well. As a third application, we obtain sparse matrices of O(1/{\epsilon}) non-zero entries as {\epsilon}-approximate solutions when optimizing any convex function over a class of diagonally dominant symmetric matrices. We show that the proposed first-order optimization technique also applies to nuclear norm and max-norm matrix optimization problems. For nuclear norm regularized optimization problems such as matrix completion and low-rank recovery, we demonstrate the practical efficiency and scalability of our algorithm for large matrix problems, as e.g. the Netflix dataset. For convex optimization over bounded matrix max-norm, our algorithm is the first with a convergence guarantee, to the best of our knowledge.

After talking to Martin , he reminded me of the following earlier paper: A Simple Algorithm for Nuclear Norm Regularized Problems by Martin Jaggi, Marek Sulovsk y. The abstract reads:

Optimization problems with a nuclear norm regularization, such as e.g. low norm matrix factorizations, have seen many applications recently. We propose a new approximation algorithm building upon the recent sparse approximate SDP solver of (Hazan, 2008). The experimental e ciency of our method is demonstrated on large matrix completion problems such as the Netflix dataset. The algorithm comes with strong convergence guarantees, and can be interpreted as a rst theoretically justi ed variant of Simon-Funk-type SVD heuristics. The method is free of tuning parameters, and very easy to parallelize.

If you want to try it out, Martin made a java implementation available here. This paper/implementation has been added to the Matrix Factorization Jungle page. From the website:

Implementation: The .java file below contains the algorithm we used for the experiments, using the power-method as the internal eigenvector procedure. The code is not yet completely self-contained, as the input data (the known/observed entries of the matrix which we want to complete) come in different formats for different datasets. The algorithm just assumes that all known entries are stored in a sequential list already. The algorithm never stores a full matrix, and therefore is able to scale to e.g. the size of the Netflix dataset.

Thanks Martin !

In the sorts of problems reminiscent of those tackled by Stefano Marchesini (he is mentioned in the acknowledgments), here is an approach to these problems as low rank/matrix completion issues. This time, the solver seems to be using nuclear norm minimization as a proxy to the rank functional even though one of the authors ( Yonina Eldar ) had pointed out that this specific proxy was not working for another area of optical imaging. Over time, I predict we are going to have specialized proxies for different areas of physics and engineering, ain't that going to be swell :-). Without further due, here is: Phase Retrieval via Matrix Completion by Emmanuel Candes, Yonina Eldar, Thomas Strohmer, Vlad Voroninski. The abstract reads:

This paper develops a novel framework for phase retrieval, a problem which arises in X-ray crystallography, diffraction imaging, astronomical imaging and many other applications. Our approach combines multiple structured illuminations together with ideas from convex programming to recover the phase from intensity measurements, typically from the modulus of the diffracted wave. We demonstrate empirically that any complex-valued object can be recovered from the knowledge of the magnitude of just a few diffracted patterns by solving a simple convex optimization problem inspired by the recent literature on matrix completion. More importantly, we also demonstrate that our noise-aware algorithms are stable in the sense that the reconstruction degrades gracefully as the signal-to-noise ratio decreases. Finally, we introduce some theory showing that one can design very simple structured illumination patterns such that three diffracted figures uniquely determine the phase of the object we wish to recover.

This week, we also have: Convex Optimization Based Low-Rank Matrix Completion and Recovery for Photometric Stereo and Factor Classification by Lun Wu, Arvind Ganesh, Boxin Shi, Yasuyuki Matsushita, Yongtian Wang, and Yi Ma. The abstract reads:

We present a new approach to robustly solve the photometric stereo problem. We cast the problem of recovering surface normals from images taken under multiple lighting conditions as a one of recovering a low-rank matrix from missing and corrupted observations, which model many different non-Lambertian effects such as shadows and specularities. Unlike previous approaches that use least-squares or heuristic robust techniques, our method uses an advanced convex optimization technique that is guaranteed to find the correct low-rank matrix by simultaneously fixing its missing and erroneous entries. Extensive experimental results demonstrate that our method achieves unprecedentedly accurate estimates of surface normals in the presence of significant amount of shadows and specularities. The new technique can be used to improve virtually any existing photometric stereo method. We not only showcase its effectiveness in the case of photometric stereo, but also extend our method to perform classification of photometric factors. In contrast to existing robust techniques, our method is computationally more efficient and provides theoretical guarantees for robustness to large errors.

The attendant site is here

Robust Principal Component Analysis? by Emmanuel Candes and Xiaodong Li, Yi Ma, John Wright. The abstract reads:

This article is about a curious phenomenon. Suppose we have a data matrix, which is the superposition of a low-rank component and a sparse component. Can we recover each component individually? We prove that under some suitable assumptions, it is possible to recover both the low-rank and the sparse components exactly by solving a very convenient convex program called Principal Component Pursuit; among all feasible decompositions, simply minimize a weighted combination of the nuclear norm and of the 1 norm. This suggests the possibility of a principled approach to robust principal component analysis since our methodology and results assert that one can recover the principal components of a data matrix even though a positive fraction of its entries are arbitrarily corrupted. This extends to the situation where a fraction of the entries are missing as well. We discuss an algorithm for solving this optimization problem, and present applications in the area of video surveillance, where our methodology allows for the detection of objects in a cluttered background, and in the area of face recognition, where it offers a principled way of removing shadows and specularities in images of faces.

Sufficient Conditions for Low-rank Matrix Recovery,Translated from Sparse Signal Recovery by  Lingchen Kong, Levent Tuncel¸ Naihua Xiu. The abstract reads:

The low-rank matrix recovery (LMR) is a rank minimization problem subject to linear equality constraints, and it arises in many fields such as signal and image processing, statistics, computer vision, system identification and control. This class of optimization problems is $NP$-hard and a popular approach replaces the rank function with the nuclear norm of the matrix variable. In this paper, we extend the concept of $s$-goodness for a sensing matrix in sparse signal recovery (proposed by Juditsky and Nemirovski [Math Program, 2011]) to linear transformations in LMR. Then, we give characterizations of $s$-goodness in the context of LMR. Using the two characteristic $s$-goodness constants, ${\gamma}_s$ and $\hat{\gamma}_s$, of a linear transformation, not only do we derive necessary and sufficient conditions for a linear transformation to be $s$-good, but also provide sufficient conditions for exact and stable $s$-rank matrix recovery via the nuclear norm minimization under mild assumptions. Moreover, we give computable upper bounds for one of the $s$-goodness characteristics which leads to verifiable sufficient conditions for exact low-rank matrix recovery.

Blind Multiband Spectrum Signals Reconstruction by Hao Shen, Thomas Arildsen, Deepaknath Tandur, and Torben Larsen. The abstarct reads:

This paper investigates sparse sampling techniques applied to downsampling and interference detection for multiband radio frequency (RF) signals. To reconstruct a signal from sparse samples is a compressive sensing problem. This paper compares three different reconstruction algorithms: 1) l_1 minimization; 2) greedy pursuit; and 3) MUltiple SIgnal Classification (MUSIC). We compare the performance of these algorithms and investigate the robustness to noise effects. Characteristics and limitations of each algorithm are discussed.

For those of you interested, there is a conference around Zurich at the end of the month entitled High-Dimensional Problems in Statistics, September 19 - 23, 2011, that features some of the work in recent matrix factorizations. 

Credit photo: NASA, Apollo 14 tracks and remains on the moon as photographed by the LRO mission. More here on LRO.

Liked this entry ? subscribe to the Nuit Blanche feed, there's more where that came from

CS: Heuristics for Rank Proxy and how it changes everything....

Work is steadily expanding from compressive sensing into low rank matrix decomposition and showing up on different approaches such as the ones dealing with time issues ( Low Rank and Compressive Imaging by Gonzalo Arce's group ) but they are not the only ones.  Recently, for instance, I mentioned the work on sub-wavelength imaging via quadratic compressive sensing at the Technion. Surely enough, this type of approach is really going beyond traditional signal processing and it requires us to learn new things.

As an aside, while the heuristics of the nuclear norm (replacing the rank functional) seems to have gotten a lot of interest in the recent algorithm development work, one should also remember that this is not the only one as shown in the recent Quadratic Compressive Sensing work and more pointedly in this 2003 paper entitled: Log-det heuristic for matrix rank minimization with applications to Hankel and Euclidean distance matrices by Maryam Fazell, Haitham Hindi, Stephen P. Boyd. I asked Yonina Eldar why they used the log-det heuristics (using CVX), and she responded that it worked better than the nuclear norm proxy. So as one can see, it looks like we are going to have a rich set of solvers in the next upcoming years, aren't we lucky, uh ? As it turns out, today we have four papers using nuclear norm heuristics to deal  with time dependent MRI and Computed Tomography. Enjoy!

An algorithm for sparse MRI reconstruction by Schatten p-norm minimization by Angshul Majumdar, Rabab K. Ward. The abstract reads:

In recent years, there has been a concerted effort to reduce the MR scan time. Signal processing research aims at reducing the scan time by acquiring less K-space data. The image is reconstructed from the subsampled K-space data by employing compressed sensing (CS)-based reconstruction techniques. In this article, we propose an alternative approach to CS-based reconstruction. The proposed approach exploits the rank deficiency of the MR images to reconstruct the image. This requires minimizing the rank of the image matrix subject to data constraints, which is unfortunately a nondeterministic polynomial time (NP) hard problem. Therefore we propose to replace the NP hard rank minimization problem by its nonconvex surrogate — Schatten p-norm minimization. The same approach can be used for denoising MR images as well. Since there is no algorithm to solve the Schatten p-norm minimization problem, we derive an efficient first-order algorithm. Experiments on MR brain scans show that the reconstruction and denoising accuracy from our method is at par with that of CS-based methods. Our proposed method is considerably faster than CS-based methods

Accelerating multi-echo T2 weighted MR imaging: Analysis prior group-sparse optimization by Angshul Majumdar, Rabab K. Ward. The abstract reads:

This works addresses the problem of reconstructing multi-echo T2 weighted MR images from partially sampled K-space data. Previous studies in reconstructing MR images from partial samples of the K-space used Compressed Sensing (CS) techniques to exploit the spatial correlation of the images (leading to sparsity in transform domain). Such techniques can be employed to reconstruct the individual T2 weighted images. However, in the current context, the different images are not independent; they are images of the same cross section, and hence are highly correlated. In this work, we not only exploit the spatial correlation within the image, but also the correlation between the images to achieve even better reconstruction results.

For individual MR images, CS based techniques lead to a sparsity promoting optimization problem in a transform domain. In this paper, we show how to extend the same framework in order to incorporate correlation between images leading to group sparsity promoting optimization. Group sparsity promoting optimization is popularly formulated as a synthesis prior problem. The synthesis prior formulation for group sparsity leads to superior reconstruction results compared to ordinary sparse reconstruction. However, in this paper we show that when group sparsity is framed as an analysis prior problem the reconstruction results are even better for proper choice of the sparsifying transform. An interesting observation of this work is that when the same sampling pattern is used to sample the K-space for all the T2 weighted echoes, group sparsity does not yield any noticeable improvement, but when different sampling patterns are used for different echoes, our proposed group sparsity promoting formulation yields significant improvement (in terms of Normalized Mean Squared Error) over previous CS based techniques.

Joint reconstruction of multiecho MR images using correlated sparsity by Angshul Majumdar, Rabab K. Ward. The abstract reads:

This works addresses the problem of reconstructing multiple T1- or T2-weighted images of the same anatomical cross section from partially sampled K-space data. Previous studies in reconstructing magnetic resonance (MR) images from partial samples of the K-space used compressed sensing (CS) techniques to exploit the spatial correlation of the images (leading to sparsity in wavelet domain). Such techniques can be employed to reconstruct the individual T1- or T2-weighted images. However, in the current context, the different images are not really independent; they are images of the same cross section and, hence, are highly correlated. We exploit the correlation between the images, along with the spatial correlation within the images to achieve better reconstruction results than exploiting spatial correlation only. For individual MR images, CS-based techniques lead to a sparsity-promoting optimization problem in the wavelet domain. In this article, we show that the same framework can be extended to incorporate correlation between images leading to group/row sparsity-promoting optimization. Algorithms for solving such optimization problems have already been developed in the CS literature. We show that significant improvement in reconstruction accuracy can be achieved by considering the correlation between different T1- and T2-weighted images. If the reconstruction accuracy is considered to be constant, our proposed group sparse formulation can yield the same result with 33% less K-space samples compared with simple sparsity-promoting reconstruction. Moreover, the reconstruction time by our proposed method is about two to four times less than the previous method.

Robust principle component analysis based four-dimensional computed tomography by Hao Gao, Jian-Feng Cai,  Zuowei Shen, and Hongkai Zhao. The abstract reads:

The purpose of this article for four-dimensional (4D) computed tomography (CT) is threefold. (1) A new spatiotemporal model is presented from matrix perspective with the row dimension in space and the column dimension in time, namely, Robust PCA based 4DCT model (Robust Principle Component Analysis based 4D CT). That is, instead of viewing the 4D object as a temporal collection of three-dimensional (3D) images and looking for local coherence in time or space independently, we perceive it as a mixture of low-rank matrix and sparse matrix to explore the maximum temporal coherence of spatial structure among phases. Here the low-rank matrix corresponds to the “background” or reference state, which is stationary over time or similar in structure; the sparse matrix stands for the “motion” or time-varying component, e.g., heart motion in cardiac imaging, which is often either approximately sparse itself or can be sparsified in the proper basis. Besides 4D CT, this Robust PCA based 4DCT model should be applicable in other imaging problems for motion reduction or/and change detection with the least amount of data, such as multi-energy CT, cardiac MRI, and hyperspectral imaging. (2) A dynamic strategy for data acquisition, i.e., a temporally spiral scheme, is proposed that can potentially maintain the similar reconstruction accuracy with much fewer projections of the data. The key point of this dynamic scheme is to reduce the total number of measurements and hence the radiation dose, by acquiring complementary data in different phases while reducing redundant measurements of the common background structure. (3) An accurate, efficient, yet simple-to-implement algorithm based on split Bregman method is developed for solving the model problem with the sparse representation in tight frames.