1 million visits on Nuit Blanche

1 million visits according to Sitemeter

from Sitemeter' site:

What is Site Meter tracking exactly?

.....Site Meter defines a "visit" as a series of page views by one person with no more than 30 minutes in between page views.

Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

PR-GAMP : Compressive Phase Retrieval via Generalized Approximate Message Passing

The following paper is hypnotic. Why ? Because had we not have a sharp phase transition, a somehow objective limit to our current knowledge, we couldn't compare the different algorithms out there and this paper would just be presenting just one algorithm against another. With the sharp phase transitions, we get to decide as a reader, that yes, I want to use this algorithm in the future because it is indeed the better solution. The second aspect of this is that they compare it with a sparse implementation of the Fienup algorithm. The algorithms by Fienup have been the mainstay of phase retrieval since the first paper came out in the mid-1980s and one isn't sure what signal structure is being reconstructed.

As an aside, James Fienup is known among other things for performing the characterization of the, then, faulty Hubble telescope [1-3] and you know how much the whole repair mission (Service Mission 1 or SM-1) hinged on me throwing the wrong M&Ms :-). 

Without further due here is the rapid and most phase transition busting algorithm in phase retrieval:

Compressive Phase Retrieval via Generalized Approximate Message Passing by Philip Schniter, Sundeep Rangan

In phase retrieval, the goal is to recover a signal $\boldsymbol{x}\in\mathbb{C}^N$ from the magnitudes of linear measurements $\boldsymbol{Ax}\in\mathbb{C}^M$. While recent theory has established that $M\approx 4N$ intensity measurements are necessary and sufficient to recover generic $\boldsymbol{x}$, there is great interest in reducing the number of measurements through the exploitation of sparse $\boldsymbol{x}$, which is known as compressive phase retrieval. In this work, we detail a novel, probabilistic approach to compressive phase retrieval based on the generalized approximate message passing (GAMP) algorithm. We then present a numerical study of the proposed PR-GAMP algorithm, demonstrating its excellent phase-transition behavior, robustness to noise, and runtime. For example, to successfully recover $K$-sparse signals, approximately $M\geq 2K\log_2(N/K)$ intensity measurements suffice when $K\ll N$ and $\boldsymbol{A}$ has i.i.d Gaussian entries. When recovering a 6k-sparse 65k-pixel grayscale image from 32k randomly masked and blurred Fourier intensity measurements, PR-GAMP achieved 99\% success rate with a median runtime of only 12.6 seconds. Compared to the recently proposed CPRL, sparse-Fienup, and GESPAR algorithms, experiments show that PR-GAMP has a superior phase transition and orders-of-magnitude faster runtimes as the problem dimensions increase.

PR-GAMP is part of the GAMPmatlab package at http://sourceforge.net/projects/gampmatlab/.

[1] "Diagnosing the Aberrations of the Hubble Space Telescope," J.R. Fienup, in J.C. Dainty, ed., Current Trends in Optics (Academic Press, London, 1994), Ch. 20, pp. 279-287. [PDF, 2 MB]

[2] "Hubble Space Telescope Characterized by Using Phase Retrieval Algorithms," J.R. Fienup, J.C. Marron, T.J. Schulz and J.H. Seldin, Appl. Opt. 32, 1747-1767 (1 April 1993). [PDF, 3.1 MB]

[3] "Phase-Retrieval Algorithms for a Complicated Optical System," J.R. Fienup, Appl. Opt. 32, 1737-1746 (1 April 1993). [PDF, 1.1 MB]

Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Compressive Wavefront Sensing with Weak Values

Ah, this is interesting:

Compressive Wavefront Sensing with Weak Values by Gregory A. Howland, Daniel J. Lum, John C. Howell

We demonstrate a wavefront sensor based on the compressive sensing, single-pixel camera. Using a high-resolution spatial light modulator (SLM) as a variable waveplate, we weakly couple an optical field's transverse-position and polarization degrees of freedom. By placing random, binary patterns on the SLM, polarization serves as a meter for directly measuring random projections of the real and imaginary components of the wavefront. Compressive sensing techniques can then recover the wavefront. We acquire high quality, 256x256 pixel images of the wavefront from only 10,000 projections. Photon-counting detectors give sub-picowatt sensitivity.

In order to reconstruct the image, they need to resort to GPSR and a TV regularization.

Thank you Sylvain for the heads-up.
Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Connections between Note by Note Cooking and Machine Learning

You probably recall this Sunday Morning Insight entry on Computational Cooking ? Well, last Friday, I attended the result of the second contest of the Note By Note Cooking (Cuisine Note a Note) organized by Herve This at AgroParisTech. It was certainly an interesting event.

In this year's event, the object was not to cook a full Note by Note dish but rather add methional to a course to be invented by the contestants.

Note by Note Cooking is the realisation that one can build food one element at a time, a little like building an image from a learned dictionary in image processing.

As usual, I had to ask questions and noted that while the final results for each contestant looked very appetizing, it seemed that the process of creating those dishes entailed much trial and error. It is not a surprise per se, but it could look very daunting to a beginner. Herve This confided that even though one could not taste all the dish from every contestant, one could figure out from certain construction that some dishes would not be tasty.

This all looks like a typical machine learning problem. So in order to know more about the subject and eventually contribute to the subject, I decided to create the first ever Note by Note Cooking meetup in Paris. It is here. It is open to all....

Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Theory of Convex Optimization for Machine Learning / Estimation in high dimensions: a geometric perspective

Sebastien Bubeck just came out with a monograph on the Theory of Convex Optimization for Machine Learning while Roman Vershynin just released the following preprint:

Estimation in high dimensions: a geometric perspective

This tutorial paper provides an exposition of a flexible geometric framework for high dimensional estimation problems with constraints. The paper develops geometric intuition about high dimensional sets, justifies it with some results of asymptotic convex geometry, and demonstrates connections between geometric results and estimation problems. The theory is illustrated with applications to sparse recovery, matrix completion, quantization, linear and logistic regression and generalized linear models.

Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Addressing FROG with Nonlinear Compressive Sensing

This has been an on-going question in the back of my mind for a while now. If you recall this line of inquiry:

• Is FROG an instance of Nonlinear Compressed Sensing ?
• A small Q&A with Rick Trebino, the inventor of FROG.
• FROG, Nonlinear Compressive Sensing ? continued.

In those entries, I wondered (and eventually talked to the person behind the technique to see) if FROG could have a sparsity based approach. As you probably recall that FROG performs a certain kind of convolution/deconvolution so as to perform pulse measurement characterization, in Rick Trebino's words:

In order to measure an event in time, you must use a shorter one. But then, to measure the shorter event, you must use an even shorter one. And so on. So, now, how do you measure the shortest event ever created?

From Rick Trebino's FROG site.

I just came across (quite late) this paper on Sparsity-based super-resolution in instruments for diagnostics of short pulses by Zohar Avnat, Pavel Sidorenko, Yoav Shechtman, Yonina Eldar, Mordechai Segev and Oren Cohen 

We demonstrate experimentally algorithmic super-resolution for diagnostics of short pulses (amplitude and phase). Our approach is based on using the measured data for finding a mathematical basis in which the pulse is represented compactly. 

In the paper, the authors used X-FROG, a technique that uses the cross correlation of the signal (i.e. the experiment requires a previously measured reference pulse.) This is different from FROG or SPIDER which, you may recall, deals with a three way correlation measurement as explained in Rick's Light-Pulse-Measurement Tutorial. 

So there is an underlying set of studies that begins to put sparsity at the center of these optical experiments. I also noted the following recent paper from Rick's publication list: M. Rhodes, S. Rahaman, P. Bowlan, G. Steinmeyer, and R. Trebino, "From femtosecond to nanosecond, laser-pulse measurement is all about the single shot," Laser Focus World 50, 97-100 (2014). The abstract reads:

Recurring misinterpretations due to the infamous coherent artifact imply that pulse-measurement methods operate best using single shot. Fortunately, such methods have recently been extended to pulses about 1 ns long—filling a gaping technological hole that has existed for almost 50 years.

From the review:

Recently, the long-overdue study of the coherent artifact in FROG and SPIDER technique occurred, and the results were shocking for many. Simulations (see Fig. 2) involved one stable train of short pulses and two unstable trains of longer pulses, the latter comprising the stable train's short pulse plus longer random components.^3,4 It was found that neither method retrieves a typical pulse in the unstable trains, but FROG's pulse lengths are at least reasonable.

What Rick et al also point out is that if the technique is so sensitive to coherent artifacts in femto-second pulses, then there is solution (some care must be taken to perform pulse characterization experiments). However they also point that the technique doesn't work well for longer pulses because greater care means more money and space. In effect, while very short (and sparse) pulses can be very well characterized, longer pulses (and not so sparse) pulses fall through the cracks even though those are key to most of the Time of Flight cameras we have mentioned here on Nuit Blanche. Rick has a FROG solution for that that also depends on second order harmonics (SHG), i.e. a three term correlation, a far cry from the usual linear or cross correlation measurment we see in traditional and nonlinear compressive sensing literature. If you have followed this thread all the way to this line, here are the questions:

• can we use some of the recent nonlinear compressive sensing approaches to tackle the current FROG system of Rick et al ?
• if that can be done, is there a theoretical limit like the Donoho-Tanner phase transition for pulse reconstruction ?
• are there nonlinearities in the enconding that can help in the sparse reconstruction process ?
• are the coherent articfact mentioned by Rick, actual information as in here ?

Rick's group code Code for Retrieving a Pulse Intensity and Phase from Its FROG Trace and their recent publications:

• 2014
• M. Rhodes, S. Rahaman, P. Bowlan, G. Steinmeyer, and R. Trebino, "From femtosecond to nanosecond, laser-pulse measurement is all about the single shot," Laser Focus World 50, 97-100 (2014).
• 2013
• M. Rhodes, G. Steinmeyer, J. Ratner, and R. Trebino, "Pulse-shape instabilities and their measurement," Laser & Photonics Reviews, doi:10.1002/lpor.201200102 (2013).
• T. C. Wong and R. Trebino, "Single-frame measurement of complex laser pulses tens of picoseconds long using pulse-front tilt in cross-correlation frequency-resolved optical gating," J. Opt. Soc. Am. B 30, 2781-2786 (2013).
• T. C. Wong and R. Trebino, "Recent Developments in Experimental Techniques for Measuring Two Pulses Simultaneously," Appl. Sci. 3, 299-313 (2013).
• 2012
• T. C. Wong, J. Ratner, and R. Trebino, "Simultaneous measurement of two different-color ultrashort pulses on a single shot," J. Opt. Soc. Am. B 29, 1889-1893 (2012).
• J. Ratner, G. Steinmeyer, T. C. Wong, R. Bartels, and R. Trebino, "The coherent artifact in modern pulse measurements," Opt. Lett. 37, 2874-2876 (2012).
• T. C. Wong, J. Ratner, V. Chauhan, J. Cohen, P. M. Vaughan, L. Xu, A. Consoli, and R. Trebino, "Simultaneously measuring two ultrashort laser pulses on a single-shot using double-blind frequency-resolved optical gating," J. Opt. Soc. Amer. B 29, 1237-1244 (2012).
• P. Piksarv, P. Bowlan, M. Lõhmus, H. Valtna-Lukner, R. Trebino, and P. Saari,"Diffraction of ultrashort Gaussian pulses within the framework of boundary diffraction wave theory," J. Opt. 14, 015701 (2012).
• J. Cohen, P. Bowlan, and R. Trebino, "Extending Femtosecond Metrology to Longer, More Complex Laser Pulses in Time and Space," IEEE J. Sel. Top. Quant. Electron. 18, 218-227 (2012).
• 2011
• P. Bowlan, and R. Trebino, "Using phase diversity for the measurement of the complete spatiotemporal electric field of ultrashort laser pulses," J. Opt. Soc. Amer. B 29, 244-248 (2012).
• P. M. Vaughan, and R. Trebino, "Optical-parametric-amplification imaging of complex objects," Opt. Expr. 19, 8920-8929 (2011).
• R. Trebino, "Optical complexity challenges pulse measurement methods," Laser Focus World (2011).
• R. Trebino, "Measuring the seemingly immeasurable," Nature Photonics 5, 189-192 (2011).
• J. Cohen, P. Bowlan, V. Chauhan, P. Vaughan, and R. Trebino, "Single-shot multiple-delay crossed-beam spectral interferometry for measuring extremely complex pulses," Opt. Comm. 284, 3785-3794 (2011).
• P. Bowlan, and R. Trebino, "Complete single-shot measurement of arbitrary nanosecond laser pulses in time," Opt. Expr. 19, 1367-1377 (2011).
• 2010
• P. Saari, P. Bowlan, H. Valtna-Lukner, M. Lõhmus, P. Piksarv, and R. Trebino, "Time-and-Space-Domain Study or Diffracting and Non-Diffracting Light Pulses," Lith. J. Phys 50, 121-127 (2010).
• P. Saari, P. Bowlan, H. Valtna-Lukner, M. Lõhmus, P. Piksarv, and R. Trebino,"Directly recording diffraction phenomena in time domain," Laser Phys. 20, 948-953 (2010).
• P. Saari, P. Bowlan, H. Valtna-Lukner, M. Lõhmus, P. Piksarv, and R. Trebino, "Basic diffraction phenomena in time domain," Opt. Expr. 18, 11083 (2010).
• M. Lõhmus, P. Bowlan, R. Trebino, H. Valtna-Lukner, P. Piksarv, and P. Saari,"Directly recording diffraction phenomena in the time domain," Lith J. Phys. 50, 69-74 (2010).
• J. Cohen, D. Lee, V. Chauhan, P. Vaughan, and R. Trebino, "Highly simplified device for measuring the intensity and phase of picosecond pulses," Opt. Expr. 18, 17484-17497 (2010).
• J. Cohen, P. Bowlan, V. Chauhan, P. Vaughan, and R. Trebino, "Measuring extremely complex pulses with time-bandwidth products exceeding 65,000 using multiple-delay crossed-beam spectral interferometry," Opt. Expr. 18, 24451-24460 (2010).
• J. Cohen, P. Bowlan, V. Chauhan, and R. Trebino, "Measuring temporally complex ultrashort pulses using multiple-delay crossed-beam spectral interferometry," Opt. Expr. 18, 6583-6597 (2010).
• V. Chauhan, J. Cohen, P. Vaughan, P. Bowlan, and R. Trebino, "Distortion-Free Single-Prism/Grating Ultrashort Laser Pulse Compressor," IEEE J. Quant. Electron. 46, 1726-1731 (2010).
• V. Chauhan, J. Cohen, and R. Trebino, "Simple dispersion law for arbitrary sequences of dispersive optics," Appl. Opt. 49, 6840 (2010).
• V. Chauhan, P. Bowlan, J. Cohen, and R. Trebino, "Single-diffraction-grating and grism pulse compressors," J. Opt. Soc. Amer. B 27, 619-624 (2010).
• P. Bowlan, and R. Trebino, "Extreme pulse-front tilt from an etalon," J. Opt. Soc. Amer. B 27, 2322-2327 (2010).
• S. Akturk, X. Gu, P. Bowlan, and R. Trebino, "Spatio-temporal couplings in ultrashort laser pulses," J. Opt. 12, 093001 (2010).

Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Videos: sub-Nyquist cognitive radio and sub-Nyquist radar systems

Yonina Eldar just sent me the following:

Dear Igor,

.....

I thought you may be interested in our two new demos which can be seen in the movies below.

They both won first place for the best ICASSP 2014 demo.

The first is a sub-Nyquist cognitive radio system which samples signals with 6Ghz Nyquist rate at 380Mhz and recovers them in real time. The second is a sub-Nyquist radar system that samples and processes radar signals with 30Mhz Nyquist rate at 1Mhz. Clutter filtering and denoising are performed at the low rate as well.

If you have any questions, I'd be happy to answer them.

Best,

Yonina

Thanks Yonina ! Here are the videos. Much of  the work is part of Yonina's Xampling project.

Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

XKCD-like comics on Compressive Sensing in MRI

Miki Lustig just sent me the following: 

Hey Igor,

While being in a creative mood recently I made a comics describing the principles of CS in MRI. It's linked from my CS page.

http://www.eecs.berkeley.edu/~mlustig/CS.html

Thought you might be interested. 

Have a nice week!

-- Miki

Outstanding Miki! I'll add it to the Learning Compressive Sensing page. The series of comics starts here. You need to click "next" below each comic to get to the next one.

Join the CompressiveSensing subreddit or the Google+ Community and post there !

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Questions and some Answers on the LinkedIn Groups (Compressive Sensing and Advanced Matrix Factorizations)

Here is a sample of questions and some answers that appeared on the compressive sensing and matrix factorization groups on LinkedIn.

Recently on The Advanced Matrix Factorization Group ( 890 members )

• John asks a question about the mathematical dual of the SVD he also pointed our attention on Butterfly Decompositions for Arbitrary Unitary Matrices
• German asked a question Regarding rank constraints in principal components pursuit

Recently on the Compressive Sensing Study Group ( 2,904 members )

• Matthieu asked about large scale computations of L1 minimization
• Rohit asked about the Computational complexity of reconstruction (which I think is for hardware)Patrick wonders about IST and AMP phase transitions
• Mrinal wonders about the the value of the constant in compressed sensing?
• Aleksandar wonders about a good implementation of the K-SVD algorithm in C/C++ for windows or clean portable...
• Zhijin wonders about a problem about the difference between CS and low-rank matrix completion
• Matija wonders about what the Powerful CS application fields are..
• WanChien wonders about Non-negative Sparse Recovery
• I wondered if Compressive Holography (was) really **that** compressive ?
• Mihai-Alexandru wondered about Maximum-entropy (recovery) method versus Compressive Sensing
• Misha wondered about if Anyone knew of a (hopefully good) reference for doing compressed sensing type reconstruction with an unknown sensing matrix?
• but to me the most interesting question is by Xuyang: Since dictionary learning is a sparse representation, is it proper to used in one-pixel imaging as a dictionary during the reconstruction?

This image was taken by Rear Hazcam: Right B (RHAZ_RIGHT_B) onboard NASA's Mars rover Curiosity on Sol 635 (2014-05-20 14:52:29 UTC).

Image Credit: NASA/JPL-Caltech

Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

PSPG: Efficient Algorithms for Robust and Stable Principal Component Pursuit Problems

Here is another implementation of the Stable Principal Component Pursuit to be added shortly to the Advanced Matrix Factorization Jungle Page.

Efficient Algorithms for Robust and Stable Principal Component Pursuit Problems by Necdet Serhat Aybat, Donald Goldfarb, Shiqian Ma

The problem of recovering a low-rank matrix from a set of observations corrupted with gross sparse error is known as the robust principal component analysis (RPCA) and has many applications in computer vision, image processing and web data ranking. It has been shown that under certain conditions, the solution to the NP-hard RPCA problem can be obtained by solving a convex optimization problem, namely the robust principal component pursuit (RPCP). Moreover, if the observed data matrix has also been corrupted by a dense noise matrix in addition to gross sparse error, then the stable principal component pursuit (SPCP) problem is solved to recover the low-rank matrix. In this paper, we develop efficient algorithms with provable iteration complexity bounds for solving RPCP and SPCP. Numerical results on problems with millions of variables and constraints such as foreground extraction from surveillance video, shadow and specularity removal from face images and video denoising from heavily corrupted data show that our algorithms are competitive to current state-of-the-art solvers for RPCP and SPCP in terms of accuracy and speed.

An implementation of PSPG is here.

Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.