Is FROG an instance of Nonlinear Compressed Sensing ?

I hope you enjoyed the videos of the past week but now that I have been thinking about different things far away from the interwebs, one subject bothered me to the point where I had to write this entry before getting back to our usual business. Quite simply I wonder if the FROG algorithm is working because the underlying signal is sparse (in some basis) ?

But I am sure you are wondering, Igor, what the *&%  FROG is ? Well, it was devised by Rick Trebino to answer the following most interesting question:

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?

After pointing out that the autocorrelation is insufficient to provide enough information in that case, our friends in ultra-short laser optics have devised a nonlinear measurement which can then be deconvoluted into a solution using some of the techniques that seemed eerily familiar to some of you who have been devising or using some of the reconstruction solvers used in compressive sensing. The main difference with generic compressive sensing is that the measurement is nonlinear. A presentation of FROG can be found here. An implementation of FROG on Matlab can be found here. More can be found on this site and in the Ultrafast Optics Textbook.

Of particular interest in this technique is the connection as to why the FROG algorithm works: It is because  it is equivalent to a two-Dimensional Phase-Retrieval Problem and that it can be resolved because of the Fundamental Theorem of Algebra (page 6-46 of this document). Furthermore, Rick seems to be looking for some help on the theoretical side::

Finally, as in the one-dimensional case, it’s important to ask how densely distributed the ambiguities are. It can be shown that the ambiguities are quite sparse, as sparse as a continuous function of one variable in a two dimensional plane. The probability of accidentally stumbling on one is very close to zero and decreases rapidly as N increases.

The two-dimensional phase-retrieval problem occurs frequently in imaging problems,[4, 65, 66, 69-73] where the squared magnitude of the Fourier transform of an image is often measured and where finite support is common. The two-dimensional phase-retrieval problem and its solution are the basis of an entire field, that of image recovery. If you’re interested in reading more on it, please check out Henry Stark’s excellent book on this subject, Image Recovery.[4]

Finally, it should be mentioned that the above argument must be modified for the FROG constraints. This has not yet been done, so a rigorous proof of essential uniqueness for FROG does not yet exist. However, thousands of pulses, many quite complex, have been retrieved using FROG, and no such ambiguities have ever been found (except for the trivial ones and a few that we will discuss that occur in SHG FROG). So don’t worry. But if you come up with a proof, please let me know.

Emphasis is mine.I also liked the fact that the method was found as a result of experimental necessities.  it is an analog measurement! Further in the book (page 6-52), one can read:

Other Time-Frequency Quantities

There are infinitely many different possible time-frequency-domain quantities. Examples include the Wigner Distribution,[81-84] the Wavelet Transform,[85, 86] and the Gabor Transform.[51, 52] Indeed, most are considered by theorists to be better, more elegant measures than the spectrogram.

For example, integrals of the Wigner Distribution over delay or frequency (the marginals) yield precisely the spectrum and intensity, respectively, which is very nice. Also, the measures just mentioned have direct inversions and don’t require an iterative algorithm. So why don’t we use one of them instead of the klunky old spectrogram? The answer is that what the spectrogram lacks in theoretical mathematical elegance, it more than makes up for in experimental optical elegance.It’s very easy to make a spectrogram in the lab. And so far no one’s figured out how to make the others, and you can bet that, if someone does, it won’t be easy. For example, making a Wigner Distribution would require making a time-reversed replica of the pulse. Making a Wavelet Transform would require that the gate pulse length be rescaled as the wavelength changes, among other complexities. All would require the measurement of negative values, which means that the signal would have to measured against a coherent background, and the measurement becomes interferometric, which adds considerable complexity. And that’s assuming we could figure out how to do it in the first place. So the spectrogram is looking a lot better now, isn’t it?

Of further interest is the following mention on page 6-72:

The solution is found by making projections, which have simple geometrical analogs. We begin with an initial guess at an arbitrary point in signal-field space (usually a signal field consisting entirely of random numbers), which typically satisfies neither constraint. In the first iteration, we make a projection onto one of the constraint sets, which consists of moving to the point in that set closest to the initial guess. From this point, we then project onto the other set, moving to the point in that set closest to the first iteration. This process is continued until the solution is reached. When the two constraint sets are convex, i.e., all line segments connecting two points in each constraint set lie entirely within the set, convergence is guaranteed. Unfortunately, the constraint sets in FROG are not convex. When a set is not convex, the projection is not necessarily unique, and a generalized projection must be defined. The technique is then called generalized projections (GP), and convergence cannot be guaranteed. Although it thus is conceivable that the algorithm may stagnate at a constant value, this approach is in practice quite robust in FROG problems.

Of note, from Compressive Sensing and Phase Retrieval by Matthew Moravec and Richard Baraniuk

And from now on, taking a cue from Rick, let us call the next reconstruction algorithm MONEY :-)

But then again,don't ask what FROG can do to nonlinear compressed sensing, ask what can FROG do to compressed sensing ? I also wonder if Justin and Rick are talking to each other ?

Of related interest are the following papers:

• Some Algorithmic Problems and Results in Compressed Sensing. by Muthu Muthukrishnan.
• Compressed Sensing with Nonlinear Observations by Thomas Blumensath
• Compressed Sensing Phase Retrieval by Matthew Moravec, Justin Romberg, and Richard Baraniuk
• Compressive Sensing and Phase Retrieval by Matthew Moravec, Richard Baraniuk
• Proximal Splitting Methods in Signal Recovery by Patrick Louis Combettes
• Monday Morning Algorithm 16: S-POCS, Using Non Convex Sparse Signal Space Instead of the Convex l1 Ball Improves POCS Recovery

And the following sites and book:

• Wikipedia on FROG, Streak Cameras, SPIDER
• SPIDER (SPIDER in scilab)