Wednesday, June 01, 2011

A lost Opportunity ?

Now that Spirit is gone, we are all relying on Opportunity to get photographs of Mars from the ground. Except, when some packets are lost. In that case, well, Opportunity gets full 2001 monolith on us as one can see from today's shots here and here.



Readers of this blog can certainly imagine what would have happened if a low power compressive sensing encoding such as the one used on PACS/Herschel had been used instead....

Credit Photo: Courtesy NASA/JPL-Caltech

Damnit Sparseman, What have you done ?

Sparseman just applied for a Google Exacycle grant. it's called Using Google Exacycle to Map a Universal Phase Transition in Compressive Sensing

Tuesday, May 31, 2011

CS: Large Scale Compressive Sensing, Robust PCA for voting in Ensemble algorithms and Spectrum Sensing

After yesterday's entry, Danny Bickson sent me the following:

One paper that is related to compressed sensing is featured here:
we are discussing how to implement parallel large scale compressed sensing where there are two feasible approaches: parallel stochastic gradient descent or parallel coordinate descent. We chose to implement the latter option (but we also compare it to the first). The paper is here: http://arxiv.org/abs/1105.5379

We have already featured the paper but you want to read Danny's blog entry.

Another entry following up on the past few days is Bob's blog entry on the voting mechanism to be used in an ensemble approach. Go read it, I'll wait.



In the comment, I mentioned an additional way we could perform this voting between different solvers' results:
Here is another suggestion, we could also put all the solutions as columns of a new matrix called B and look for a factorization of that matrix as: B = A + E + Z , where A is a low rank matrix (rank 1), E is a sparse matrix and Z is a "noisy" matrix ( http://perception.csl.uiuc.edu/matrix-rank/sample_code.html ) or B = A + E (Robust PCA, http://www-stat.stanford.edu/~candes/papers/RobustPCA.pdf ). Of note the comparison between different algorithms: http://perception.csl.uiuc.edu/matrix-rank/sample_code.html#Comparison
Of related interest:






Gonzalo Vazquez Vilar is continuing his spectrum sensing summary presented at ICASSP in Cooperative spectrum sensing and resource allocation at ICASSP 2011

Monday, May 30, 2011

Compressive Sensing Literature This Week.

With the end of the semester for several universities we have some theses showing up on the radar screen. We also have a new crop of blog entries, papers and presentations. At the end some of the papers are marginally connected to compressive sensing but they are interesting. Finally, there is a announcement for a workshop. First things first, Danny Bickson has a blog, it is:
http://bickson.blogspot.com/

Following up on last week, here are two other summaries of the sublinear algorithm conference in Italy:




Now onto the papers/preprints:

We propose Shotgun, a parallel coordinate descent algorithm for minimizing L1-regularized losses. Though coordinate descent seems inherently sequential, we prove convergence bounds for Shotgun which predict linear speedups, up to a problem-dependent limit. We present a comprehensive empirical study of Shotgun for Lasso and sparse logistic regression. Our theoretical predictions on the potential for parallelism closely match behavior on real data. Shotgun outperforms other published solvers on a range of large problems, proving to be one of the most scalable algorithms for L1.
Compressive Identification of Linear Operators by Reinhard Heckel, Helmut Bölcskei. The abstract reads:
We consider the problem of identifying a linear deterministic operator from an input-output measurement. For the large class of continuous (and hence bounded) operators, under additional mild restrictions, we show that stable identifiability is possible if the total support area of the operator's spreading function satisfies D <= 1/2. This result holds for arbitrary (possibly fragmented) support regions of the spreading function, does not impose limitations on the total extent of the support region, and, most importantly, does not require the support region of the spreading function to be known prior to identification. Furthermore, we prove that asking for identifiability of only almost all operators, stable identifiability is possible if D <= 1. This result is surprising as it says that there is no penalty for not knowing the support region of the spreading function prior to identification.


A signal recovery method for compressive sensing under noisy measurements is proposed. The problem is formulated as a nonconvex nonsmooth constrained optimization problem that uses the smoothly clipped absolute deviation (SCAD) function to promote sparsity. Relaxation is employed by means of a series of local linear approximations (LLAs) of the SCAD in a constrained formulation. The relaxation is shown to converge to a minimum of the original nonconvex constrained optimization problem. In order to solve each nonsmooth convex relaxation problem, a second-order cone programming (SOCP) formulation is used, which can be applied by using standard state-of-the-art SOCP solvers such as SeDuMi. Experimental results demonstrate that signals recovered using the proposed method exhibit reduced ℓ∞ reconstruction error when compared with competing methods such as ℓ1-Magic. Simulations demonstrate that significant reduction in the reconstruction error can be achieved with computational cost that is comparable to that required by
the ℓ1-Magic algorithm.

We present and analyze an e cient implementation of an iteratively reweighted least squares algorithm for recovering a matrix from a small number of linear measurements. The algorithm is designed for the simultaneous promotion of both a minimal nuclear norm and an approximatively low-rank solution. Under the assumption that the linear measurements ful ll a suitable generalization of the Null Space Property known in the context of compressed sensing, the algorithm is guaranteed to recover iteratively any matrix with an error of the order of the best k-rank approximation. In certain relevant cases, for instance for the matrix completion problem, our version of this algorithm can take advantage of the Woodbury matrix identity, which allows to expedite the solution of the least squares problems required at each iteration. We present numerical experiments which con rm the robustness of the algorithm for the solution of matrix completion problems, and demonstrate its competitiveness with respect to other techniques proposed recently in the literature.

The attendant (code) is here.


We show that sparse spherical harmonic expansions can be efficiently recovered from a small number of randomly chosen samples on the sphere. To establish the main result, we verify the restricted isometry property of an associated preconditioned random measurement matrix using recent estimates on the uniform growth of Jacobi polynomials.

We consider the synthesis problem of Compressed Sensing { given s and an M £ n matrix A, extract from A an m £ n submatrix Am, with m as small as possible, which is s-good, that is, every signal x with at most s nonzero entries can be recovered from observation Amx by `1 minimization: x = argminufkuk1 : Amu = Amxg. We show that under reasonable assumptions the synthesis problem can be reformulated as the problem of entry-wise approximation, within a given accuracy, of n £ n matrix W = YT A, with Y 2 RM£n given, by a matrix of the form YT m Am, with Am comprised of m rows of A. We propose randomized algorithms for efficiently solving the latter problem with accuracy guaranties EfkW ¡YT m Amk1g · O(1)L(Y; A) qln(n)m Here L(Y; A) is an easy-to-specify quantity which in good cases . is a moderate absolute constant (e.g., L(A; A) = 1 when A is the Hadamard matrix, and similarly for the matrix of Fourier transform on any finite Abelian group). We also supply derandomized versions of the approximation algorithms which do not require random sampling of matrices and attain the same accuracy bounds. We further demonstrate that in terms of approximation accuracy our algorithms are optimal up to logarithmic in n factors. Finally, we provide preliminary numerical results on the performance of our algorithms for the synthesis problem.

For compressed sensing with jointly sparse signals, we present a new signal model and two new joint iterative greedy-pursuit recovery algorithms. The signal model is based on the assumption of a jointly shared support-set and the joint recovery algorithms have knowledge of the size of the shared support-set. Through experimental evaluation, we show that the new joint algorithms provide significant performance improvements compared to regular algorithms which do not exploit a joint sparsity.
Estimation of the level set of a function (i.e., regions where the function exceeds some value) is an important problem with applications in digital elevation maps, medical imaging, and astronomy. In many applications, however, the function of interest is acquired through indirect measurements, such as tomographic projections, coded-aperture measurements, or pseudo-random projections associated with compressed sensing. This paper describes a new methodology and associated theoretical analysis for rapid and accurate estimation of the level set from such projection measurements. The proposed method estimates the level set from projection measurements without an intermediate function reconstruction step, thereby leading to significantly faster computation. In addition, the coherence of the projection operator and McDiarmid’s inequality are used to characterize the estimator’s performance. 

A key theorem regarding the Restricted Isometry Property for short sampling trajectories contained a normalization error which renders the statement of the theorem incorrect. This note describes the original claim and proof, the normalization issue and how it impacts the proof, and several avenues for future investigation.


Consider an m by N matrix Phi with the Restricted Isometry Property of order k and level delta, that is, the norm of any k-sparse vector in R^N is preserved to within a multiplicative factor of 1 +- delta under application of Phi. We show that by randomizing the column signs of such a matrix Phi, the resulting map with high probability embeds any fixed set of p = O(e^k) points in R^N into R^m without distorting the norm of any point in the set by more than a factor of 1 +- delta. Consequently, matrices with the Restricted Isometry Property and with randomized column signs provide optimal Johnson-Lindenstrauss embeddings up to logarithmic factors in N. In particular, our results improve the best known bounds on the necessary embedding dimension m for a wide class of structured random matrices; for partial Fourier and partial Hadamard matrices, we improve the recent bound m = O(delta^(-4) log(p) log^4(N)) appearing in Ailon and Liberty to m = O(delta^(-2) log(p) log^4(N)), which is optimal up to the logarithmic factors in N. Our results also have a direct application in the area of compressed sensing for redundant dictionaries.



Presentations:

The three theses are:

 SONAR Imaging using Compressive Sensing by  Taylor Williams. The abstract reads::
Sonar imaging is a technique that can locate objects in a scene from their acoustic reflections. It utilizes multiple measurements from different angles to create a 2D image. Conventional imaging algorithms such as backprojection (BP) require a large number of measurements to produce accurate images. Theory indicates that an alternative approach called compressive sensing (CS) can create accurate images using just a fraction of the measurements. CS requires that the scene is compressible and that each individual measurement provides information about the scene, not just a particular location. The sonar imaging experiment must be designed to meet these requirements. The purpose of this study is to show that the compressive sensing framework can be used in sonar imaging with results comparable to conventional methods. A sonar test stand was built that can measure acoustic reflections from a scene. A pseudo-random noise (PN) code was used for transmission. Four speakers and 16 microphones were mounted randomly perturbed from a circle surrounding the scene. Software was developed to create an image from this data through FBP. Also, a CS algorithm was developed to reconstruct an image from limited measurements. This algorithm uses a random subset of samples from each measurement. Initial results show that FBP can effectively be used to image a scene using acoustic waves. The CS algorithm yields a similar quality image using less than 10% of the measurements. These results show that CS can be used in sonar imaging to greatly reduce the number of measurements that need to be collected. The findings are directly portable to radar imaging, a field with a high level of research for both military and civilian uses

Magnetic resonance imaging (MRI) is a powerful tool for studying the anatomy, physiology, and metabolism of biological systems. Despite the fact that MRI was introduced decades ago and has already revolutionized medical imaging, current applications are still far from utilizing the full potential of the MR signal. Traditional MRI data acquisition and image reconstruction methods are based on simple Fourier inversion, leading to undesirable trade-offs between image resolution, signal-to-noise ratio (SNR), and data acquisition time. Classical approaches to addressing these trade-offs have relied on improved imaging hardware and more efficient pulse sequences. In contrast, our work addresses the limitations of MR using relatively less-explored signal processing approaches, which have recently become practical because of increasing computational capabilities. This dissertation concerns the use of constrained imaging models to guide the design of both data acquisition and image reconstruction, leading to improved imaging performance in the context of both noise-limited and resolution-limited scenarios. To address noise limitations for high-resolution imaging, we introduce a quasi-Bayesian edge-preserving smoothness prior for modeling correlated image sequences. The prior models the correlated edge structures that are observed in the image sequence, and is used within a penalized maximum likelihood framework to reduce image noise while preserving high-resolution anatomical structure. In contrast to many constrained imaging methods, we demonstrate that the proposed method is relatively simple to analyze and is robust to model inaccuracy when reconstruction parameters are chosen appropriately. Resolution and SNR analysis shows that the proposed formulations lead to substantial improvements in SNR with only a moderate decrease in spatial resolution. An examination of resolution and SNR trade-offs is presented, which serves as a guide for the optimal design of data acquisition and image reconstruction procedures in this context. To address limited spatial resolution in high-SNR scenarios, we design specialized data acquisition and image reconstruction procedures to enable image reconstruction from sparsely-sampled data. Specifically, we leverage prior information that the image has sparse or low-rank structure to significantly reduce sampling requirements in two different contexts. In the first context, we assume that the image is sparse in a known transform domain, and develop a novel non-Fourier data acquisition scheme to enable high-quality reconstruction from undersampled data. The second context is specific to spatiotemporal imaging, and it is assumed that the temporal evolution of the spatiotemporal image is highly correlated at different spatial positions. This correlation leads to the formulation of a novel low-rank matrix recovery problem, which we demonstrate can be solved efficiently and effectively using special algorithms. Applications of the proposed techniques are illustrated with simulated and experimental data from a variety of different MR imaging scenarios.

And an older Master's thesis: Image compression and recovery using compressive sampling and particle swarm optimization. by Benjamin Van Ruitenbeek,. The abstract reads: 
We present a novel method for sparse signal recovery using Particle Swarm Optimization and demonstrate an application in image compression. Images are compressed with compressive sampling, and then reconstructed with particle swarm techniques. Several enhancements to the basic particle swarm algorithm are shown to improve signal recovery accuracy. We also present techniques specifically for reconstructing sparse image data and evaluate their performance.
Not strictly related to CS:
In this paper we present a multi-scale dictionary learning paradigm for sparse and redundant signal representations. The appeal of such a dictionary is obvious - in many cases data naturally comes at different scales. A multi-scale dictionary should be able to combine the advantages of generic multiscale representations (such as Wavelets), with the power of learnt dictionaries, in capturing the intrinsic characteristics of a family of signals. Using such a dictionary would allow representing the data in a more efficient, i.e. sparse, manner, allowing applications to take a more global look at the signal. In this work we aim to achieve this goal without incurring the costs of an explicit dictionary with large atoms. The K-SVD using Wavelets approach presented here applies dictionary learning in the analysis domain of a fixed multi-scale operator. This way, sub-dictionaries at different data scales, consisting of small atoms, are trained. These dictionaries can then be efficiently used in sparse coding for various image processing applications, potentially outperforming both single-scale trained dictionaries and multi-scale analytic ones. In this paper we demonstrate this construction and discuss its potential through several experiments performed on fingerprint and coastal scenery image
Audio Inpainting by Amir Adler, Valentin Emiya, Maria G. Jafari, Michael Elad, Remi Gribonval and Mark D. Plumbley. The abstract reads:
We propose the Audio Inpainting framework that recovers audio intervals distorted due to impairments such as impulsive noise, clipping, and packet loss. In this framework, the distorted samples are treated as missing, and the signal is decomposed into overlapping time-domain frames. The restoration problem is then formulated as an inverse problem per audio frame. Sparse representation modeling is employed per frame, and each inverse problem is solved using the Orthogonal Matching Pursuit algorithm together with a discrete cosine or a Gabor dictionary. The performance of this algorithm is shown to be comparable or better than state-of-the-art methods when blocks of samples of variable durations are missing. We also demonstrate that the size of the block of missing samples, rather than the overall number of missing samples, is a crucial parameter for high quality signal restoration. We further introduce a constrained Matching Pursuit approach for the special case of audio declipping that exploits the sign pattern of clipped audio samples and their maximal absolute value, as well as allowing the user to specify the maximum amplitude of the signal. This approach is shown to outperforms state-of-the-art and commercially available methods for audio declipping

Finally here is an announcement for a meeting at the intractability center:
Workshop : Counting, Inference and Optimization on GraphsMay 26, 2011 by admin
Filed under Events, Highlights, News, Workshops
Leave a Comment
Nov Nov
2 5
November 2 – 5, 2011
The aim of this multidisciplinary workshop is to bring together various communities who work on counting, inference, and optimization problems related to graphs. These communities include
- Theoretical computer science
- Information/coding theory
- Statistical physics
- Statistical inference
During this 3.5-day-long workshop at the Princeton Center for Computational Intractability, topics will include holographic algorithms, complexity dichotomy theorems, capacity of constrained coding schemes, graphical models and belief propagation algorithms, and the computation of partition functions in classical and quantum physics.



Credit: NASA, this is one of the most amazing shot I have seen of the international space station. You can see both the Space shuttle, the European ATV and the Russian Soyuz docked to it (you will probably not see this after June) . Other photos taken by Ron an astronaut during one of his extra-vehicular activity can be found here.(via NASA Watch)

Saturday, May 28, 2011

Great Thoughts Friday: Kickstarter as a way to fund some of these crazy projects

I was thinking about this yesterday, but did not get around to writing this entry before today. So it really is a Great Thoughts Friday entry. 

Some of you may not know about Kickstarter. it is a site where one features project that requests funding from people on the interwebs. Examples for the technology or photography section include:











Following some of the themes mentioned here, what could be some of the crazy projects thast could be funded through Kickstarter ?

  • an iPad/iPod app that downloads automatically all the pdfs featured on nuit blanche for offline viewing
  • fly a high altitude balloon to get a hemispherical view of the horizon
  • development of a platform to be flown on a high altitude balloon to allow for an on board camera to be directed from the ground
  • support travel for travel and cost of living if needed for Sparseman. if he sends something to the Google Exacycle program
  • build a multispectral imager out of an iPhone4.
  • ?????


Ensemble, We Can Be the Dumbest: The Google Exacycle Program.

In French, ensemble means together, so the title of this entry is really meant as a semi translation of yesterday's "Together We Can Be the Dumbest" entry. Bob points out that his ensemble method and the DUMBEST algorithm don't seem to match whereas I point out that they seem to be the same thing. In short, once you have a certain number of measurements, all of us have noticed empirically that solutions found by two solvers differed and that only the knowledge of the initial solution makes us say which algorithm is better than the other. The problem with this approach is really that if you were to use a random lens imager, you probably couldn't make out the real solution. A system that uses as much as what you have already gathered is an important improvement over what I should call oracle based systems or spending resources getting an additional measurement. Hence the need to efficiently use what you already have by using subsets of a measurements through several solvers.

I note that this idea is so important that folks like Yilun Wang and Wotao Yin have recognized it and made a solver out of this idea (ISD). They even made it clear as to when they came up with the idea on their website, something I usually don't see often. Similarly, the use of all the measurements you already have seems to also be there in the Kalman filter and beyond work of Namrata Vaswani et al .

Figure is from Recovery of Compressively Sensed Sparse Signals using Cyclic OLS[1]

Anyway, in about the same way an ensemble solver was first on the leaderboard of the Netflix prize (but did not win), we ought to collectively investigate how the flurry of solvers can help us do better reconstruction and map better DT phase transitions. This should not work only for sparse signals reconstruction as we ought to also consider doing the same approach for the current crop of  structured sparsity, MMV, robust PCA and Matrix Completion solvers. The real question is: Is the reason an acronym like DUMBEST won't get funded the same reason why somebody investigating Ensemble behavior won't garner much support ? If it is, then all y'all ought to consider the Google Exacycle program. Imagine that even if you are in love with one algorithm (yours :-)), an ensemble approach could be to merge the result of that same solver using different parameters (and we know how some of these parameters are important sometimes) in an approach parallel to epsilon photography. The possibilities are so endless, that the 100 million CPU hours now don't look as large as one would think. The other part of it is I don't know of one problem in engineering and applied math that 

  • has so many repercussions on so many problems, while at the same time
  • is embarrassingly parallel.

If nobody tells me they are sending something to the Google exacycle program, I'll send a placeholder. This is important.

Friday, May 27, 2011

Together We Can Be the Dumbest

I used to call it the DUMBEST algorithm, Bob calls it an ensemble algorithm [1], this is so refined, so elegant ... I like it.


Credit: NASA

Through the Non Looking-Glass, and What Alice Found There

The story goes that Lewis Caroll gave a copy of "Alice in Wonderland" to Queen Victoria who then asked him in return to send her his next book as she fancied the first one. The joke is that the book was "An Elementary Treatise on Determinants, With Their Application to Simultaneous Linear Equations and Algebraic Equations". Sir Lewis Caroll then went on to write a follow-on to Alice in Wonderland called "Through the Looking-Glass, and What Alice Found There" that features a chess board.


And then it all aligned in one fell swoop a little like Alice falling in a different magic world of wonders. That chess board reminded me of the grid used in the compressive coded aperture work mentioned yesterday in Rebecca Willett's work[2][3].



The simultaneous linear equations reminded me of the obvious connection to compressive sensing and underdetermined linear systems of equations. The determinant functional of the second book reminded of the current solution technique using the rank proxy log(det) [1] to recover image from a quadratic compressive sensing approach and finally, the looking glass is nothing short of a lens. What is linking of these elements ? Quite simply: Lens Free imaging [5][6][7].

And so what did Alice found through the Non Looking Glass you ask ? Initially there are some successes but eventually we have to deal with the pesky details, actually those were details when using lenses, they are now your main issues and the way you solve for them is what makes you famous. These pesky details are ?

  • Since we are getting non human readable image, we need to perform calibration to figure out if what we see is what we want. The issue is that we have to form a combinatorial amount of trials to since now the transfer function is not symmetric or has no known features [9].
  • Noise gets in the way as found by the earlier folks who have done coded aperture for the past fifty years [4] since now the PSF is widespread. You lose resolution with a lens system but this is because you are decreasing noise.

Let us also note that these issues are similar to the ones we face when looking at other radiation than light[8].

[6] Lens-free optical tomographic microscope with a large imaging volume on a chip by Serhan O. Isikmana, Waheb Bisharaa, Sam Mavandadia, Frank W. Yua, Steve Fenga, Randy Laua, and Aydogan Ozcan
[7] Lensfree on-chip holography facilitates novel microscopy applications by Aydogan Ozcan, Serhan Isikman, Onur Mudanyali, Derek Tseng and Ikbal Sencan

Thursday, May 26, 2011

CS: Institute of Advanced Studies' Women and Mathematics Courses

The Institute of Advanced Studies' Women and Mathematics series of lectures and seminars featured the following interesting presentations this year:

Sublinear Algorithms 2011 Summaries


Jelani Nelson blogs some summaries about Sublinear Algorithm 2011 in Italy. Here is what we have so far:







Credit: NASA / JPL / UA, Spirit's specular reflection
When HiRISE took a photo of Spirit's resting spot in Gusev crater on March 31, 2011, it happened to be in exactly the right position to catch a specular reflection (a glint) from the rover's solar panels. Apart from being pretty, it signifies that there was not a thick coating of dust on the panels.

Printfriendly