Thursday, October 21, 2010

CS: Compressed sensing for wide-field radio interferometric imaging

Today we have a more in-depth look at interferometry using a sphere as a support and its connection to Compressive Sensing in Compressed sensing for wide-field radio interferometric imaging by Jason D. McEwen, Yves Wiaux. The abstract reads:

For the next generation of radio interferometric telescopes it is of paramount importance to incorporate wide field-of-view (WFOV) considerations in interferometric imaging, otherwise the fidelity of reconstructed images will suffer greatly. We extend compressed sensing techniques for interferometric imaging to a WFOV and recover images in the spherical coordinate space in which they naturally live, eliminating any distorting projection. The effectiveness of the spread spectrum phenomenon, highlighted recently by one of the authors, is enhanced when going to a WFOV, while sparsity is promoted by recovering images directly on the sphere. Both of these properties act to improve the quality of reconstructed interferometric images. We quantify the performance of compressed sensing reconstruction techniques through simulations, highlighting the superior reconstruction quality achieved by recovering interferometric images directly on the sphere rather than the plane.

I note from their conclusion:

...Extensions to realistic and continuous visibility coverage and their impact on compressed sensing based interferometric imaging are now of considerable importance. In general, compressed sensing addresses imaging by optimising both reconstruction and acquisition, while we have essentially focused on reconstruction only. The possibility of optimising the configuration of interferometers to enhance the spread spectrum phenomenon for compressed sensing reconstruction is an exciting avenue of research at the level of acquisition. In addition, direction dependent beam e ects may also provide an alternative source of the spread spectrum phenomenon...

Wednesday, October 20, 2010

CS: Sub-Nyquist Sampling of Short Pulses, Xampling and Traditional Compressive Sensing

Here is an interesting paper, after the hardware implementation of Xampling in the Modulated WideBand Converter here is some more on the subject of Xampling that seems to follow the generalized sampling theory and provide sub-nyquist sampling results.


We develop sub-Nyquist sampling systems for analog signals comprised of several, possibly overlapping, finite duration pulses with unknown shapes and time positions. Efficient sampling schemes when either the pulse shape or the locations of the pulses are known have been previously developed. To the best of our knowledge, stable and low-rate sampling strategies for a superposition of unknown pulses without knowledge of the pulse locations have not been derived. The goal in this two-part paper is to fill this gap. We propose a multichannel scheme based on Gabor frames that exploits the sparsity of signals in time and enables sampling multipulse signals at sub-Nyquist rates. Our approach is based on modulating the input signal in each channel with a properly chosen waveform, followed by an integrator. We show that, with proper preprocessing, the Gabor coefficients necessary for almost perfect reconstruct of the input signal, can be recovered from the samples using standard methods of compressed sensing. In addition, we provide error estimates on the reconstruction and analyze the proposed architecture in the presence of noise. The resulting scheme is flexible and exhibits good noise robustness. The first part in this series is focused on the basic underlying principles. The second part generalizes the present sampling system in several directions. In particular, we consider practical implementations from a hardware perspective and extend the architecture to efficiently sample radar-like signals that are sparse in both time and frequency.
My Arxiv filter now include the Xampling keyword. In the following paper: Xampling: Analog Data Compression by Moshe Mishali and Yonina Eldar there is simple parallel between Xampling and compressive Sensing. The abstract of the paper reads:
We introduce Xampling, a design methodology for analog compressed sensing in which we sample analog bandlimited signals at rates far lower than Nyquist, without loss of information. This allows compression together with the sampling stage. The main principles underlying this framework are the ability to capture a broad signal model, low sampling rate, e cient analog and digital implementation and lowrate baseband processing. In order to break through the Nyquist barrier so as to compress the signals in the sampling process, one has to combine classic methods from sampling theory together with recent developments in compressed sensing. We show that previous attempts at sub-Nyquist sampling su er from analog implementation issues, large computational loads, and have no baseband processing capabilities. We then introduce the modulated wideband converter which can satisfy all the Xampling desiderata. We also demonstrate a board implementation of our converter which exhibits sub-Nyquist sampling in practice.


 From that paper, I note the following comparison with traditional Compressed Sensing:
....Exploiting sparsity for rate reduction has been explored in the context of CS, which treats underdetermined sparse recovery. The signal model assumes a vector x of nite length n, which has only a few nonzero entries. Sensing is carried out by computing the linear projection y = Ax, with A having far fewer rows than columns. Results from this fi eld [11, 12] show that under suitable conditions, the linear sensing is stably invertible, even when the length of y is proportional to the number of nonzeros in x, rather than the ambient dimension n. However, it is not straightforward to generalize the discrete CS formulation to analog signals. The difficulty can be noticed immediately in the signal model. Sparsity is de ned in CS by counting the number of nonzeros in x, while analog sparsity of x(t) involves an uncountable number of zeros and nonzeros. Naive extensions of CS-type algorithms for sparse recovery to in nite dimensions leads to unde ned or difficult problems [14]. Discretization methods result in very large scale CS systems, which impose a severe burden on the digital processing units.
The CS paradigm aims at avoiding high-rate redundant sampling. The discrete CS framework [11,12] initiated a long line of highly in uential works. However, it still remains puzzling from the analog sampling viewpoint; sensing by y = Ax implicity assumes that x is the Nyquist rate samples of some continuous signal x(t) on a specific time-interval. We propose Xampling as a general framework within various solutions for analog signals can be compared according to the four rules (X1)-(X4).....

Version 2 also came out Xampling: Signal Acquisition and Processing in Union of Subspaces by Moshe Mishali, Yonina C. Eldar, Asaf Elron. The abstract reads:
We introduce Xampling, a unified framework for signal acquisition and processing of signals in a union of subspaces. The main functions of this framework are two. An analog projection narrows down the input bandwidth prior to sampling with commercial devices. A nonlinear algorithm detects the input subspace prior to conventional signal processing. We build the framework bottom-up, from the application layer to the abstract setting, in three steps. First, we study Xampling for lowrate signal acquisition by conducting a thorough comparative study between two sub-Nyquist acquisition strategies, the random demodulator and the modulated wideband converter (MWC), in terms of model robustness and hardware and software complexities. Second, we develop an algorithm that enables convenient signal processing at sub-Nyquist rates from samples obtained by the MWC. Third, with the intuition we gain from the previous stages, we describe the line of reasoning underlying the proposed Xampling framework. In addition, we show that a variety of sampling approaches for union classes fit nicely into our framework, supporting the generality of Xampling.

Image Credit: NASA/JPL/Space Science Institute, N00164548.jpg was taken on September 25, 2010 and received on Earth September 26, 2010. The camera was pointing toward TITAN at approximately 246,162 kilometers away, and the image was taken using the CL1 and CB3 filters.

Tuesday, October 19, 2010

CS: Parallel Camp, SCM, NASA Reduced Gravity Opportunity, Around the Blogs in 80 hours, Apprentissage et Parcimonie

I am probably going to go to the Parallel Camp in two days from now but I am not sure what I want to talk about nor what I want to get out of meeting people that are into GPUs. However, If I make a presentation, I will feature it here.. The day before there will be a meeting at SCM entitled "Les limites de la modélisation" (in french), I look forward to the talk on MOX.

I made pitch for the HASP flight recently (Imaging Earth from 120,000 feet: Four Years Later.), but if instead of having hardware flying at 100,000 you prefer go a joy ride in Microgravity, you may want to think of a experiment that could fly on NASA's Reduced Gravity Aircraft (yes the vomit comet), as I said before, make sure you know why you are doing that if you are qualified:

NASA seeks undergraduates to defy gravity for Science and Engineering: Proposals Due October 27

The Reduced Gravity Student Flight Opportunities Program provides a unique academic experience for undergraduate students to successfully propose, design, fabricate, fly and evaluate a reduced gravity experiment of their choice.  Application deadline, flight dates, and other important dates for the 2011 Campaign have been announced.  Please share this information with faculty and students.

Letters of Interest (Optional) Due:         September 22, 2010
Proposals Due:                                          October 27, 2010
Announcement of Selected Teams:      December 8, 2010
Flight Week:                                                 June 2-11, 2011
Information about the program and the application process can be found on the microgravity website (http://microgravityuniversity.jsc.nasa.gov/).


The blog entries you may have missed:
  • First, I agree with Andrew, this essay by Mandelbrot is fascinating
    A maverick’s apprenticeship. The Wolf Prize for Physics. Edited by David Thouless. Singapore: World Scientific, 2004. [ PDF (154.4 KB) ]

Finally, Remi Gribonval pointed out to the upcoming meeting next week (in French)

Apprentissage et Parcimonie

Date : 2010-11-10
Lieu : Telecom Paristech - B312
Thèmes scientifiques :
A - Méthodes et modèles en traitement de signal

Annonce

Les représentations parcimonieuses des signaux et des images reposent sur l'utilisation de dictionnaires redondants de formes d'ondes typiques de certaines classes de signaux ou d'images. Leur utilisation a connu un essor considérable ces dernières années notamment dans les domaines de la restauration, de la compression, de la séparation de sources et des problèmes inverses. Il existe de forts liens, notamment algorithmiques, entre ces modèles parcimonieux et la théorie statistique de l'apprentissage et de la sélection de modèle, et ses applications en apprentissage automatique.
L'objectif global de la journée est de favoriser la rencontre entre les communautés françaises du traitement du signal / de l'apprentissage statistique qui participent de concert au développement rapide du concept de parcimonie et à ses applications, depuis les fondement statistiques et théoriques jusqu'aux dernières avancées algorithmiques.
La journée sera organisée autour d'exposés invités qui permettront de dessiner l'état de l'art du domaine et des défis à venir.

Programme

Organisateurs: Rémi Gribonval et Francis Bach.
  • 09h30-10h10 - Stéphane Mallat, Classification with Sparse or Invariant Representations ?
  • 10h10-10h50 - Odalric Maillard, Least-Squares regression with random spaces
  • 10h50-11h10 Pause café
  • 11h10-11h50 - Matthieu Kowalski, Parcimonie et structures pour les décompositions des signaux dans des dictionnaires temps-fréquence
  • 11h50-12h30 - Guillaume Obozinski, Parcimonie structurée et apprentissage de dictionnaire
  • 14h00-14h40 - Jean-Christophe Pesquet, Algorithmes parallèles proximaux et applications
  • 14h40-15h20 - Erwan Lepennec, Estimation de densité par méthode de Dantzig à pénalisation minimale
  • 15h20-15h40 Pause café
  • 15h40-16h20 - Onur Dikmen, Maximum marginal likelihood estimation for nonnegative dictionary learning
  • 16h20-17h00 - Alexandre Tsybakov, Estimation de matrices de faible rang en grande dimension

Monday, October 18, 2010

CS: The long entry of the week.

 Here are the papers and preprints that popped up in the past few days, some are connected directly to compressive others ...not so much.

Compressed sensing (CS) samples signals at a much lower rate than the Nyquist rate if they are sparse in some basis. In this paper, the CS methodology is applied to sinusoidally modeled audio signals. As this model is sparse by definition in the frequency domain (being equal to the sum of a small number of sinusoids), we investigate whether CS can be used to encode audio signals at low bitrates. In contrast to encoding the sinusoidal parameters (amplitude, frequency, phase) as current state-of-the-art methods do, we propose encoding few randomly selected samples of the time-domain description of the sinusoidal component (per signal segment). The potential of applying compressed sensing both to single-channel and multichannel audio coding is examined. The listening test results are encouraging, indicating that the proposed approach can achieve comparable performance to that of state-of-the-art methods. Given that CS can lead to novel coding systems where the sampling and compression operations are combined into one low complexity step, the proposed methodology can be considered as an important step towards applying the CS framework to audio coding applications.
Compressed Sensing for OFDM UWB Systems by Tanish Agrawal, Vishwas Lakkundi, Anthony Griffin, and Panagiotis Tsakalides. The abstract reads:
This paper considers compressed sensing (CS) techniques for signal reconstruction and channel estimation in OFDM-based high-rate ultra wideband (UWB) communication systems. We employ a parallel CS structure that exploits frequency domain sparsity. We also consider multipath UWB channels in both the line-of-sight and non line-of-sight environments. UWB signal detection and channel estimation from sub-Nyquist analog projections is carried out using an optimized orthogonal matching pursuit algorithm and the smoothed l_0 algorithm. Simulation results demonstrate significant gains in the form of reliable signal recovery and channel estimation as well as dramatically sub-Nyquist sampling rates for the analog-to-digital converters while maintaining high data rates.

This paper exploits recent developments in sparse approximation and compressive sensing to efficiently perform localization in wireless networks. Particularly, we re-formulate the localization problem as a sparse approximation problem using the compressive sensing theory that provides a new paradigm for recovering a sparse signal solving an l_1 minimization problem. The proposed received signal strength-based method does not require any time specific/propriatery hardware since the location estimation is performed at the Access Points (APs). The experimental results show that our proposed method, when compared with traditional localization schemes results in a better accuracy in terms of the mean localization error.

Recovering or estimating the initial state of a highdimensional system can require a potentially large number of measurements. In this paper, we explain how this burden can be significantly reduced for certain linear systems when randomized measurement operators are employed. Our work builds upon recent results from the field of Compressive Sensing (CS), in which a high-dimensional signal containing few nonzero entries can be efficiently recovered from a small number of random measurements. In particular, we develop concentration of measure bounds for the observability matrix and explain circumstances under which this matrix can satisfy the Restricted Isometry Property (RIP), which is central to much analysis in CS. We also illustrate our results with a simple case study of a diffusion system. Aside from permitting recovery of sparse initial states, our analysis has potential applications in solving inference problems such as detection and classification of more general initial states.

In the theory of compressed sensing, restricted isometry analysis has become a standard tool for studying how efficiently a measurement matrix acquires information about sparse and compressible signals. Many recovery algorithms are known to succeed when the restricted isometry constants of the sampling matrix are small. Many potential applications of compressed sensing involve a data-acquisition process that proceeds by convolution with a random pulse followed by (nonrandom) subsampling. At present, the theoretical analysis of this measurement technique is lacking. This paper demonstrates that the $s$th order restricted isometry constant is small when the number $m$ of samples satisfies $m \gtrsim (s \log n)^{3/2}$, where $n$ is the length of the pulse. This bound improves on previous estimates, which exhibit quadratic scaling.


Spectrum sensing is a fundamental component in cognitive radio. A major challenge in this area is the requirement of a high sampling rate in the sensing of a wideband signal. In this paper a wideband spectrum sensing model is presented that utilizes a sub-Nyquist sampling scheme to bring substantial savings in terms of the sampling rate. The correlation matrix of a finite number of noisy samples is computed and used by a subspace estimator to detect the occupied and vacant channels of the spectrum. In contrast with common methods, the proposedmethod does not need the knowledge of signal properties that mitigates the uncertainty problem. We evaluate the performance of this method by computing the probability of detecting signal occupancy in terms of the number of samples and the SNR of randomly generated signals. The results show a reliable detection even in low SNR and small number of samples.

Sampling theories lie at the heart of signal processing devices and communication systems. To accommodate high operating rates while retaining low computational cost, efficient analog-to digital (ADC) converters must be developed. Many of limitations encountered in current converters are due to a traditional assumption that the sampling state needs to acquire the data at the Nyquist rate, corresponding to twice the signal bandwidth. In this thesis a method of sampling far below the Nyquist rate for sparse spectrum multiband signals is investigated. The method is called periodic non-uniform sampling, and it is useful in a variety of applications such as data converters, sensor array imaging and image compression. Firstly, a model for the sampling system in the frequency domain is prepared. It relates the Fourier transform of observed compressed samples with the unknown spectrum of the signal. Next, the reconstruction process based on the topic of compressed sensing is provided. We show that the sampling parameters play an important role on the average sample ratio and the quality of the reconstructed signal. The concept of condition number and its effect on the reconstructed signal in the presence of noise is introduced, and a feasible approach for choosing a sample pattern with a low condition number is given. We distinguish between the cases of known spectrum and unknown spectrum signals respectively. One of the model parameters is determined by the signal band locations that in case of unknown spectrum signals should be estimated from sampled data. Therefore, we applied both subspace methods and non-linear least square methods for estimation of this parameter. We also used the information theoretic criteria (Akaike and MDL) and the exponential fitting test techniques for model order selection in this case.

$\ell_1$ minimization can be used to recover sufficiently sparse unknown signals from compressed linear measurements. In fact, exact thresholds on the sparsity, as a function of the ratio between the system dimensions, so that with high probability almost all sparse signals can be recovered from i.i.d. Gaussian measurements, have been computed and are referred to as "weak thresholds" \cite{D}. It has also been known that there is a tradeoff between the sparsity and the $\ell_1$ minimization recovery stability in terms of the signal vector tail component. In this paper, we give a \emph{closed-form} characterization for this tradeoff which we call the scaling law for compressive sensing recovery stability. In a nutshell, we are able to show that as the sparsity backs off $\varpi$ ($0<\varpi<1$) from the weak threshold of $\ell_1$ recovery, the parameter for the recovery stability will scale as $\frac{1}{\sqrt{1-\varpi}}$. Our result is based on a careful analysis through the Grassmann angle framework for the Gaussian measurement matrix. We will further discuss how this scaling law helps in analyzing the iterative reweighted $\ell_1$ minimization algorithms. If the nonzero elements over the signal support follow a probability density function (pdf) $f(\cdot)$ whose $t$-th derivative $f^{t}(0) \neq 0$ for some $t \geq 0$, then a certain iterative reweighted $\ell_1$ minimization algorithm can be analytically shown to lift the phase transition thresholds (weak thresholds) of the plain $\ell_1$ minimization algorithm. Using the scaling law for the sparse recovery stability, this extends our earlier results of weak threshold improvements for sparse vectors with nonzero elements following the Gaussian distribution, whose pdf is itself nonzero at the origin (namely its $0$-th derivative is nonzero).

An information theoretic perspective on group testing problems has recently been proposed by Atia and Saligrama, in order to characterise the optimal number of tests. Their results hold in the noiseless case, where only false positives occur, and where only false negatives occur. We extend their results to a model containing both false positives and false negatives, developing simple information theoretic bounds on the number of tests required. Based on these bounds, we obtain an improved order of convergence in the case of false negatives only. Since these results are based on (computationally infeasible) joint typicality decoding, we propose a belief propagation algorithm for the detection of defective items and compare its actual performance to the theoretical bounds.

Error Prediction and Model Selection via Unbalanced Expander Graphs by Yohann de Castro. The abstract reads:
We investigate deterministic design matrices for the fundamental problems of error prediction and model selection. Our deterministic design matrices are constructed from unbalanced expander graphs, and we wonder if it is possible to accurately estimate the response and the support of our target vector using computationally tractable algorithms. We show that for any adjacency matrix of an unbalanced expander graph and any target vector, the lasso and the Dantzig selector satisfy oracle inequalities in error prediction and model selection involving the largest (in magnitude) coefficients of the target, i.e. upper bounds in term of the best sparse approximation. Our oracle inequalities allow error prediction with an accuracy which is the best, up to a logarithmic factor, one could expect knowing the support of the target. From a practical standpoint, these estimators can be computed by solving, either a simple quadratic program for the lasso, or a linear program for the Dantzig selector. Our results are non-asymptotic and describe the performance one can expect in all cases.
Low-rank matrix recovery via iteratively reweighted least squares minimization by Massimo Fornasier, Holger Rauhut, Rachel Ward. The abstract reads:
We present and analyze an efficient 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 fulfill 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 that confirm 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.

Despite the recent progress towards efficient multiple kernel learning (MKL), the structured output case remains an open research front. Current approaches involve repeatedly solving a batch learning problem, which makes them inadequate for large scale scenarios. We propose a new family of online proximal algorithms for MKL (as well as for group-lasso and variants thereof), which overcomes that drawback. We show regret, convergence, and generalization bounds for the proposed method. Experiments on handwriting recognition and dependency parsing testify for the successfulness of the approach.

On the Construction of Finite Oscillator Dictionary by Rongquan Feng, Zhenhua Gu, Zilong Wang, Hongfeng Wu, Kai Zhou. The abstract reads:
A finite oscillator dictionary which has important applications in sequences designs and the compressive sensing was introduced by Gurevich, Hadani and Sochen. In this paper, we first revisit closed formulae of the finite split oscillator dictionary $\mathfrak{S}^s$ by a simple proof. Then we study the non-split tori of the group $SL(2,\mathbb{F}_p)$. Finally, An explicit algorithm for computing the finite non-split oscillator dictionary $\mathfrak{S}^{ns}$ is described.

An Almost Optimal Unrestricted Fast Johnson-Lindenstrauss Transform by Nir Ailon, Edo Liberty. The abstract reads:
The problems of random projections and sparse reconstruction have much in common and individually received much attention. Surprisingly, until now they progressed in parallel and remained mostly separate. Here, we employ new tools from probability in Banach spaces that were successfully used in the context of sparse reconstruction to advance on an open problem in random pojection. In particular, we generalize and use an intricate result by Rudelson and Vershynin for sparse reconstruction which uses Dudley's theorem for bounding Gaussian processes. Our main result states that any set of $N = \exp(\tilde{O}(n))$ real vectors in $n$ dimensional space can be linearly mapped to a space of dimension $k=O(\log N\polylog(n))$, while (1) preserving the pairwise distances among the vectors to within any constant distortion and (2) being able to apply the transformation in time $O(n\log n)$ on each vector. This improves on the best known $N = \exp(\tilde{O}(n^{1/2}))$ achieved by Ailon and Liberty and $N = \exp(\tilde{O}(n^{1/3}))$ by Ailon and Chazelle.
The dependence in the distortion constant however is believed to be suboptimal and subject to further investigation. For constant distortion, this settles the open question posed by these authors up to a $\polylog(n)$ factor while considerably simplifying their constructions. 

Random projection methods give distributions over k d matrices such that if a matrix      (chosen according to the distribution) is applied to a nite set of vectors xi 2 Rd the resulting vectors     xi 2 Rk approximately preserve the original metric with constant probability. First, we show that any matrix (composed with a random 1 diagonal matrix) is a good random projector for a subset of vectors in Rd. Second, we describe a family of tensor product matrices which we term Lean Walsh. We show that using Lean Walsh matrices as random projections outperforms, in terms or running time, the best known current result (due to Matousek) under comparable assumptions.
Riemannian geometry applied to BCI classification by Alexandre Barachant, Stéphane Bonnet, Marco Congedo, and Christian Jutten. The abstract reads:
In brain computer interface based on motor imagery, covariances matrices are widely used through spatial filters computation and other signal processing methods. Covariances matrices lie in the space of Semi-definite Positives (SPD) matrices and therefore, fall within the Riemannian geometry domain. Using a differential geometry frameworks, we propose different algorithms in order to classify covariances matrices in their native space.




Image Credit: NASA/JPL/Space Science Institute , W00065756.jpg was taken on October 14, 2010 and received on Earth October 15, 2010. The camera was pointing toward TITAN at approximately 207,643 kilometers away, and the image was taken using the CB3 and CL2 filters.

Sunday, October 17, 2010

CS: Compressed Sensing in Low-Light Imaging

Rebecca Willett's talk on "Compressed Sensing in Low-Light Imaging" at the Duke Compressive Sensing Workshop of a year and half ago is now on YouTube (all other presentations are on Flash hosted at the Duke site and hence are not readable on iPod/iPhone/iPads). Much of the talk presents some of the more complete information in Compressive Optical Imaging: Architectures and Algorithms by Roummel Marcia, Rebecca Willett, and Zachary Harmany.



Saturday, October 16, 2010

Benoit Mandelbrot

I met Benoit Mandelbrot twenty years ago for a few minutes. I was then a young student of science and he was making a presentation on fractals on campus (according to his resume it was in 1990). He wasn't invited by the physics or some engineering department but some enlightened soul decided he should be a featured speaker at the MSC. Most of the audience knew about fractals already so the presentation was really just a rehash of things we had already read but it was just exciting to hear him speak on the matter. Fractals are one of the few things that talks to people irrespective to their background. After his talk, I started something I have not stopped doing since: I asked him a question. As it turns out, I realized from our interaction that asking a question was the best compliment you could make a presenter. It shows that the subject of the presentation moved you so much that you'd rather ignore all kinds of social rules and face ridicule than not have an answer to your burning question. In fact, the presenter and his response should make it worthwhile for you to cross that threshold. I understood that when I asked that question to Mandelbrot. Even though it was a very basic question, Mandelbrot took it seriously and patiently answered it. That day, I realized that all this conditioning from my French upbringing of censoring oneself and not questionning openly scientific "authorities" was misplaced. It was a very liberating experience. An experience that I continue mimicking on this very blog and the meetings I attend.

I have my own thought about Fractals and was in the process of writing another small entry on compressed sensing and fractals at some point in time after having watched recently Hunting the Hidden Dimension. But the thought of Mandelbrot's disappearance makes this a little heavier than I initially thought.

Hunting the Hidden Dimension can be watched on Google Video here.


(Thanks Shubbendu)

By the way, let it be known once and for all, that Mandelbrot's initial illustration of fractals was utilizing the coast of  Brittany not Britain's.
Bon Voyage Monsieur Mandelbrot.

Good Taste in All Manners this Week

Echoing last week's Good Taste In All Manners This Week., here is this week's list of sites from which readers came. The following pages and blogs link to or cited Nuit Blanche..

I hereby officially decree their authors to have good taste in all manners.

You can be on that distinguished list too!

In no particular order:

Friday, October 15, 2010

Imaging Earth from 120,000 feet: Four Years Later.




Just the other day I was wondering how some off the shelf technology had evolved over the past four years. My gold standard is when we flew one of the best and one of the cheapest (less than $500) camera with the largest optical zoom aboard a NASA helium balloon. Four years ago, that camera was the Canon S2 IS (it is the camera in this box). It had a 5MP sensor and a 12X optical zoom and could take a 4GB SD disk. We set out to have a rig that could fire the camera every twenty seconds for the next nine hours (out of twenty, some of these hours are at night!). A little Rube Goldberg'ish set up, but it worked flawlessly:



And we got these beautiful pictures from 120,000 feet. The resolution for this 12X optical zoom at 120,000 feet was pretty like the notch before last in Google Maps as shown in this entry (or about a 1 meter resolution).  Here is a presentation my undergrad students presented then:



The site for GEOCAM is here. The attendant blog is here. All the photos can be used for research purposes and featured some interesting elements (like a plane in this shot)

What do we have for the same price four years later ? The Canon SX30IS : a 14.1MP Digital Camera with a  35x wide optical zoom. So about four years later, we can have a camera that is 3 times better in both resolution and zoom. Wow! If we could extrapolate, this camera could provide about 1 foot resolution (30 cm) or probably enough to see a larger sign than this one or this one. In terms of memory, our limit was 8GB (we got a 4GB instead and 1600 photos) but nowadays, you can buy a 32 GB card for less than $100 ( the Transcend 32 GB goes for $65, while the Sandisk 32GB goes for $85) and a 64GB for less than $300 (the SanDisk 64GB goes for $299, the Kingston 64 GB goes for $218 ).4GB got us 1600 photos at 5 MP, so a  32GB SD disk could shoot about 4200 photos and a 64GB could shoot about 8400 photos. Imagine the type of pictures and maps you could get flying this thing at 120,000 feet up. If you are in the U.S. working with some undergrad students you could probably do this as the HASP folks are looking for payloads for the upcoming HASP/NASA balloon. The difference between this balloon and a home made one is that this one will probably fly for 20 hours covering more than 200 miles of terrain. This means that you could probably beat our world record.

From Greg Guzik
Please find attached here the Call for Payloads (CFP) for the September 2011 flight of the High Altitude Student Platform (HASP).  HASP can support up to 12 student payloads (providing power, telemetry and commanding) during a flight to an altitude of 124,000 feet for up to 20 hours.  Details about previous HASP flights and the student payloads flown can be found on the “Flight Information” page of the HASP website at http://laspace.lsu.edu/hasp/Flightinfo-2010.php    Details on the payload constraints and interface with HASP can be found on the “Participant Info” page of the HASP website at http://laspace.lsu.edu/hasp/Participantinfo.php
Applications are due December 17, 2010 and selections will be announced by mid-January 2011.
If you have any questions about the application materials or HASP, feel free to contact us at guzik@phunds.phys.lsu.edu
We will also be conducting a Q&A Teleconference about HASP and the application process on Friday, November 12, 2010 at 10:00 am (central time).  Groups who have previously flown on HASP as well as new organizations should plan on attending this teleconference.  To participate, dial in to 1-866-717-2684 a few minutes prior to the conference time.  When requested enter the conference ID number 6879021 followed by the # key.
Also please forward this e-mail to any others that you fee might be interested in applying.
Cheers,
Greg Guzik
Ps: Please note that we are still intending to fly HASP 2010 payloads during May 2011.

The main reason the photographs taken during our flight are unique revolves around the fact that the data is free for anybody to use and because satellite imagery uses push broom technology as opposed to full square CCDs. The big difference between these types of shots and those taken from low flying drones and planes is the ability to image a larger swath of land (the balloons at an altitude three times higher than the altitude flown by long range commercial aircrafts) and a low cost camera that does not require GPS or compass ( In When You Become the Map I made the case that if you stitch enough photos together then you don't need to be integrated to Google Earth/Maps, you have just produced a new map yourself) making it a potential tool for rapid imaging by the citizenry in case of disaster. We showed that the making of maps could be done very simply by feeding all our stock photos directly to Autopano Pro (that still costs about $100). We actually pushed the envelope of that software (and talked at length with their dev people) then but I think looking at what it can do nowadays, it could handle 8000 x 14 MP photos.

Thursday, October 14, 2010

CS: Weak Compressive Sensing

I have been asked by some of you if this or that maybe an instance of weak compressive sensing as discussed yesterday. Let's make it short, an example of weak compressive sensing measurement matrix is:

P( I + \epsilon A )

with P a projection operator (it takes only a random set of rows from its argument), I is the identity matrix, A a gaussian matrix. With \epsilon = 0, we have strict inpaiting whereas with very large \epsilon we asymptotically have some measurement matrix used in Compressive Sensing. Among the different things I'd ask somebody who would look into this type of construction:


Wednesday, October 13, 2010

When is Inpainting an Instance of Weak Compressed Sensing ?

Here is my question: When is inpainting an instance of weak compressed sensing ? By weak compressive sensing, I mean that the sampling process is a multiplexing of sorts but it is "weak" in that the  contribution of the multiplexing is small compared to one single element. To make this "definition" clearer:
  • a weak compressive sensing measurement matrix that can be thought as a selection of rows of the sum of the identity matrix and an epsilon times a gaussian matrix.
  • a measurement matrix for strict inpainting would be a selection of rows of the identity matrix.
This is a discussion that started earlier this year as an extension of the example coming out of the Wired article. I wrote about it in Compressed Sensing or Inpainting ? Part I and in Compressed Sensing or Inpainting, part II. In that last entry, I mentioned
...This is why I wrote this example in Compressed Sensing: How to wow your friends back in 2007 that features an example with delta and sines. Let us note that in Compressive Sensing Audio, for the delta/sines assumption to hold, you really need have to sample enough within time-localized phenomena. In other words, Compressed Sensing is not a license to make appear something you did not catch with the sampling process. This needs to be said often, as in MRI or steady-state audio, the signal is being sampled with diracs in their appropriate phase spaces (Fourier for MRI and time for Audio) that will get you a result directly applicable by a compressive sensing approach. In other fields like imagery however, you do not sample directly in a good phase space and you need new types of exotic hardware to perform these new types of incoherent measurements...
then I asked the question

Is your average point and click camera with missing pixels a compressive sensing system ?

And finished the entry with:
 Eventually the question is "are lower quality cameras or microphones "weak" compressive sensing systems " ? More to come later...
Yesterday, the thought crossed my mind as I was reading the paper on a microscope that can achieve superresolution but that looks like, and is claimed to be, strict inpainting. We have had similar occurrences before. (they are listed below:) At the heart of  this issue is the question of whether the reconstruction involves information that has been acquired incoherently (CS) or information that is made up but is simple enough:

Here are occurences of strict inpainting, whereby data have been synthetically removed or cannot have been acquired in the first place:
These are all synthetic cases, but in the case of a real hardware like the superresolution microscope (featured in Far-Field Microscopy of Sparse Subwavelength Objects by Alexander Szameit, Yoav Shechtman, H. Dana, S. Steiner, S. Gazit, T. Cohen-Hyams, E. Bullkich, O. Cohen, Yonina C. Eldar, S. Shoham, E. B. Kley, M. Segev. and  Super-Resolution and Reconstruction of Sparse Sub-Wavelength Images by Snir Gazit, Alexander Szameit, Yonina Eldar, Mordechai Segev.,) are we seeing an instance of:
  • Strict inpainting: Information at the smallest scale is irretrievably lost as the authors claim , or
  • Weak Compressive Sensing: i.e. some of the smaller scale information is included in the "low resolution" performed by the microscope and is therefore there for use by the reconstruction process.
In this case, the answer seems to be the second option. From the strict inpainting examples above, we know that the l_1/l_0 solvers bring back some level of reasonability but at what point, an analog device like the microscope is taking up information that eventually provides better than reasonable information as opposed to simply a reasonable expectation ? The answer may lie in the calibration process.


Image Credit: NASA/JPL/Space Science Institut, N00164124.jpg was taken on October 08, 2010 and received on Earth October 10, 2010.

Printfriendly