CS:Q&A with Tim Lin, Dantzig Selector and DT ?

In the comment section of the entry featuring the results of the LASSO in the mutliplicative noise effect on the Donoho-Tanner Phase transition, Tim Lin kindly asked the following question:

I'm interested in knowing what "solving LASSO" entails, ie, how is your regularization/constraint parameter chosen? It seems like it would be a pretty crucial component of your results, unless you are solving SPGL1 to completion, but then you would be solving bpdn?

To what I responded:

Hello Tim,

Thanks for asking this question. I guess you are asking what paramrter \tau I am using (in the spgl1 sense)?

My known solution is an instance of zeros and ones. I also know the sparsity of the "unknown" vector beforehand, so I know what the \tau parameter should be. So in essence, I am really showing the best DT transition since I know the exact \tau parameter when I ask SPGL1 to solve my problem. Does that answer your question ?

Cheers,

Igor.

Tim then responded with:

Ah yes, so this is an "oracle" lasso solution. That makes sense now, thanks!

Ps: the implications of this on really large systems that experience numerical roundoff errors is very scary!

Tim is really nice, he diplomatically calls it an "oracle",

As for numerical roundoffs on very large systems this may indeed be an issue. While watching the videos of Emmanuel Candes and Vincent Rivoirard, I was reminded of this work Sparse Recovery in Linear Models with Matrix Uncertainty by Alexandre Tsybakov and Mathieu Rosenbaum. The main paper is here. Maybe I ought to look into the Dantzig Selector in the multiplicative noise influence on the Donoho-Tanner phase transition.

Credit: NASA/Johns Hopkins University Applied Physics Laboratory/Carnegie Institution of Washington

CS: A Q&A with Felix Herrmann, SMALLbox

I took the opportunity of Felix Herrmann sending me the job opportunities for graduate studentship and postdocs to ask a question destined for people on the applied side of things:.

Felix,

The question applies specifically to the applied folks. In most systems that are being solved, we somehow hope that the RIP or some such property holds for our system so we can get on the solving of actual problems. It's all great and fun to pretend that but in the end nobody is really convince of the matter.

So here are my questions: In order to be more convincing, have you tried to show that your systems followed the Donoho-Tanner phase transition ? in the negative, is it because of time constraints or something else ?

Felix kindly responded with:

Hi Igor,

....

I have always been a fan of the phase diagram by Donoho/Tanner because they capture the recovery conditions for typical sparse vectors and acquisition matrices. This means they are less pessimistic and they reflect practical situations better.

However, in my field we are confronted with problem sizes that make it impossible to compute complete phase diagrams. In addition, we are typically relying on redundant sparsifying transformations for which the theory is relatively under developed.

Having said this, I looked in a recent paper at the "oversampling ratio" between the percentage of coefficients required to get a particular nonlinear approximation error and the degree subsampling required to get the same error. I borrowed this idea from Mallat's book and adapted it to the seismic problem. In principle, this sort of thing is somewhat similar to phase diagrams and it gives some assurances but I am afraid maybe not the type of assurances acquisition practitioners are looking for.

While useful, the method I presented in the paper is expensive to compute and does not really lead to a workflow that would provide practical principles to design acquisition scenarios based on compressive sampling. For instance, I am not aware of practical (read computationally feasible and doable in the field) ways to do QC etc. So in summary, while CS provides beautiful insights I think we still have a long way to go to bring this technology into the main stream.

Thanks Felix !
 
The paper is: Randomized sampling and sparsity: getting more information from fewer samples by Felix Herrmann. The abstract reads:

Many seismic exploration techniques rely on the collection of massive data volumes that are subsequently mined for information during processing. While this approach has been extremely successful in the past, current efforts toward higher resolution images in increasingly complicated regions of the Earth continue to reveal fundamental shortcomings in our workflows. Chiefly amongst these is the so-called “curse of dimensionality” exemplified by Nyquist’s sampling criterion, which disproportionately strains current acquisition and processing systems as the size and desired resolution of our survey areas continues to increase. In this paper, we offer an alternative sampling method leveraging recent insights from compressive sensing towards seismic acquisition and processing for data that are traditionally considered to be undersampled. The main outcome of this approach is a new technology where acquisition and processing related costs are no longer determined by overly stringent sampling criteria, such as Nyquist. At the heart of our approach lies randomized incoherent sampling that breaks subsampling related interferences by turning them into harmless noise, which we subsequently remove by promoting transform-domain sparsity. Now, costs no longer grow significantly with resolution and dimensionality of the survey area, but instead depend on transform-domain sparsity only. Our contribution is twofold. First, we demonstrate by means of carefully designed numerical experiments that compressive sensing can successfully be adapted to seismic exploration. Second, we show that accurate recovery can be accomplished for compressively sampled data volumes sizes that exceed the size of conventional transform-domain data volumes by only a small factor. Because compressive sensing combines transformation and encoding by a single linear encoding step, this technology is directly applicable to acquisition and to dimensionality reduction during processing. In either case, sampling, storage, and processing costs scale with transform-domain sparsity. We illustrate this principle by means of number of case studies.

On a different note, the SMALLbox toolbox was announced at the LVA conference. From the twitter feed:

SMALLbox provides a common API for various sparsity toolboxes like sparco, sparselab, etc.

From the website:

Sparse Models, Algorithms, and Learning for

Large-scale data (SMALL)

SMALL will develop a new foundational framework for processing signals, using adaptive sparse structured representations.
A key discriminating feature of sparse representations, which opened up the horizons to new ways of thinking in signal processing including compressed sensing, has been the focus on developing reliable algorithms with provable performance and bounded complexity.

Yet, such approaches are simply inapplicable in many scenarios for which no suitable sparse model is known. Moreover, the success of sparse models heavily depends on the choice of a "dictionary" to reflect the natural structures of a class of data, but choosing a dictionary is currently something of an "art", using expert knowledge rather than automatically applicable principles. Inferring a dictionary from training data is key to the extension of sparse models for new exotic types of data.

SMALL will explore new generations of provably good methods to obtain inherently data-driven sparse models, able to cope with large-scale and complicated data much beyond state-of-the-art sparse signal modelling. The project will develop a radically new foundational theoretical framework for the dictionary-learning problem, and scalable algorithms for the training of structured dictionaries. SMALL algorithms will be evaluated against state-of-the art alternatives and we will demonstrate our approach on a range of showcase applications. We will organise two open workshops to disseminate our results and get feedback from the research community.

The framework will deeply impact the research landscape since the new models, approaches and algorithms will be generically applicable to a wide variety of signal processing problems, including acquisition, enhancement, manipulation, interpretation and coding. This new line of attack will lead to many new theoretical and practical challenges, with a potential to reshape both the signal processing research community and the burgeoning compressed sensing industry.

Credit: SpaceX, Test firing of a Merlin 1C regeneratively cooled rocket engine on a single engine vertical test stand at the SpaceX test facility in McGregor, Texas. The next Falcon flight will occur no earlier than November 8th.

CS: Q&A with Pierre Vandergheynst about the CS-ECG system

[Update: Dear Hackaday readers, this ECG system is an instance of compressive sensing, where the encoding is very low power while the power hungry decoding of the signal is performed off line. A normal system requires the encoding of the signal (a power hungry process) to be performed during acquisition before sending the signal out.  The iPhone is a central piece and serves as a full scale computer . It performs state of the art optimization computations (l_1 minimization with wavelet frames) to decode the signal. ]


Following up on yesterday's entry on the CS-ECG trade studies performed by Pierre Vandergheynst at EPFL, and because of my commentary, I decided to ask him the following questions:

Pierre,

You may have noticed my remark on the blog about the CS-ECG. Yet, I think I am misunderstanding some part of the slide. Namely the right figure on this slide:

From your trade studies, you make the statement that CS is marginally better than no compression but I don't understand the point being made with the figure on the right. Can you enlighten me ?

Pierre kindly answered with

The improvement was only marginal for the msp430 system which revealed that its micro controller is too greedy in terms of power with respect to the antenna. However we show in the fig on the right that using truly low power microcontrollers can lead to dramatic reduction in power consumption: as the cs encoder becomes 7 to 8 times more efficient than an optimized wavelet coder...it was the first step in a more ambitious project. Second step is to build an analog to digital system that will use analog CS to sample the ECG, hence removing the power hungry a2d step

 I then asked:

Do you think this idea of classifier as an app has some legs  (Note: I personally do from experience)? Also can you also enlighten me as to why you are jailbreaking the iPhone, i.e. what part of the system is not currently available from the Apple API ?

Pierre answered

In fact the idea of performing classification on the measurements directly (if this is what you mean) is certainly very interesting and that is one of the directions in our bio cs node project. The idea would be to have a very reactive system that would just classify the heart signals and then if a specific situation is detected by the classifier the whole signal can be reconstructed, archived or sent to a physician.

As for the iPhone, the main problem was the bluetooth layer. Apple does not let you easily use it for general purpose communication. We thus had to break it to implement our own protocol.

All in all, I hope people realize that this is a complete system implementation from A to Z, and that using CS can become a crucial technology in a real life environment. It shows that there are many intricate but interesting issues when deploying CS in such a complete application.

 Thanks Pierre !

At the very least if a classifier is too difficult to implement on the multiple unhealthy cases revealed by an EKG, then a classifier could at the very least identify only those parts of the EKG traces when the heart is healthy. On a different note, I'll add this system on the compressive sensing hardware page.


If you think this blog provides a service, please support it by ordering through the Amazon - Nuit Blanche Reference Store

CS: The long post of the week (Q&A, Blog Entries, Book, Preprints)

On LinkedIn we have the following questions:

• Tanish asks a question on the Complexity of SL0 algorithm
• Ma asks a question on How to simulate the image acquisition process

Maybe Tanish's question can be answered in the Theory CS Q&A,

On MetaOptimize Q&A, there is a long question on Compressed Sensing of Communities in a Network

Some blog entries got my attention recently:

Djalil

• Gaussians and matrix completion
• Souvenirs d’un évalué médiocre  (where we read the remarks of Bernard Beauzamy who I have mentioned in the EPH entries)

Alex

• The gist of the Laplace transform method for bounding eigenvalues of random matrices
• Positivity of a certain integral
• Comparing products of gaussian moments with one gaussian moment
• A Matrix Cauchy-Schwarz Inequality via Schur Complements
• Nasty matrix moment!
• Convergence of eigenvalues of sample covariance matrices
• Eigenvalues of sums of random matrices

Andrew

• A new efficient lossless compression algorithm

Bob

• A Briefly Annotated Timeline of Similarity Search in Time Series
• Paper of the Day (Po'D): Minimum Distances in High-Dimensional Musical Feature Spaces Edition
• Paper of the Day (Po'D): Audio Signal Representations for Indexing in the Transform Domain Edition
• Paper of the Day (Po'D): Sound Retrieval and Ranking Using Sparse Auditory Representations Edition
• EUSIPCO 2010 update

in the last entry one can read:

Martin Vetterli gave the most humorous talk, and at the same time trumpeted a very important message: Reproducible Research. If we as scientists put in a little extra effort to make the results and algorithms described in our publications clearly available, either by sufficient description, or by downloadable software, and if we make meaningful and sufficient comparisons with other algorithms where appropriate, then we will simultaneously improve the quality of our work, and increase our achievements. As an added bonus, the evidence suggests that research made reproducible is cited more, and more quickly than research that is not; and that once you have started making your research reproducible, the time it takes you the next time decreases. The idea isn't all roses though, as the vast majority of reproducible research is in the form of MATLAB code. I am lucky to have an institution license, but many others are not. There is also the fact that one day the various websites with code that we point to in our papers will not exist any longer.

Highlights are mine. With this state of the affairs and issues like the ones mentioned  in Why do commercial CT scanners still employ traditional, filtered back-projection for image reconstruction?. by Xiaochuan Pan, Emil Sidky and Michael Vannier or the inability to run the wonderful  numerical tours of Gabriel Peyre if you don't have a matlab licence or cannot install Scilab (on the iPad for instance). I am wondering and probably starting to implement a solution that might be answering some of these issues...Stay tuned....

In a different direction, a book entitled:GPU Computing Gems Edited by Wen-mei W Hwu is coming out in December and will feature a chapter on compressed sensing reconstruction:

Chapter 45: ℓ1 Minimization in ℓ1-SPIRiT Compressed Sensing MRI Reconstruction

I have added it to the Nuit Blanche - Amazon Store in case you want to order it.

Here is a list of papers that showed up on my radar screen for your enjoyment:

Hard thresholding pursuit: an algorithm for Compressive Sensing by Simon Foucart. The abstract reads:

We introduce a new iterative algorithm to find sparse solutions of underdetermined linear systems. The algorithm, a simple combination of the Iterative Hard Thresholding algorithm and of the Compressive Sampling Matching Pursuit or Subspace Pursuit algorithms, is called Hard Thresholding Pursuit. We study its general convergence, and notice in particular that only a finite number of iterations are required. We then show that, under a certain condition on the restricted isometry constant of the matrix of the system, the Hard Thresholding Pursuit algorithm indeed finds all s-sparse solutions. This condition, which reads \delta_3s < 1=p3, is heuristically better than the sufficient conditions currently available for other Compressive Sensing algorithms. It applies to fast versions of the algorithm, too, including the Iterative Hard Thresholding algorithm. Stability with respect to sparsity defect and robustness with respect to measurement error are also guaranteed under the condition \delta_3s < 1=p3. We conclude with some numerical experiments to demonstrate the good empirical performance and the low complexity of the Hard Thresholding Pursuit algorithm.

Explicit constructions of RIP matrices and related problems by Jean Bourgain, Stephen J. Dilworth, Kevin Ford, Sergei Konyagin and Denka Kutzarova.. The abstract reads:

We give a new explicit construction of $n imes N$ matrices satisfying the Restricted Isometry Property (RIP). Namely, for some c \gt 0, large N and any n satisfying N^{1-c} \lt n \lt N, we construct RIP matrices of order k^{1/2+c}. This overcomes the natural barrier k=O(n^{1/2}) for proofs based on small coherence, which are used in all previous explicit constructions of RIP matrices. Key ingredients in our proof are new estimates for sumsets in product sets and for exponential sums with the products of sets possessing special additive structure. We also give a construction of sets of n complex numbers whose k-th moments are uniformly small for 1le kle N (Turan's power sum problem), which improves upon known explicit constructions when (log N)^{1+o(1)} le nle (log N)^{4+o(1)}. This latter construction produces elementary explicit examples of n by N matrices that satisfy RIP and whose columns constitute a new spherical code; for those problems the parameters closely match those of existing constructions in the range (log N)^{1+o(1)} le nle (log N)^{5/2+o(1)}.

Collaborative Spectrum Sensing from Sparse Observations in Cognitive Radio Networks by Jia Meng, Wotao Yin, Husheng Li, Ekram Hossain, Zhu Han. The abstract reads:

Spectrum sensing, which aims at detecting spectrum holes, is the precondition for the implementation of cognitive radio (CR). Collaborative spectrum sensing among the cognitive radio nodes is expected to improve the ability of checking complete spectrum usage. Due to hardware limitations, each cognitive radio node can only sense a relatively narrow band of radio spectrum. Consequently, the available channel sensing information is far from being sufficient for precisely recognizing the wide range of unoccupied channels. Aiming at breaking this bottleneck, we propose to apply matrix completion and joint sparsity recovery to reduce sensing and transmitting requirements and improve sensing results. Specifically, equipped with a frequency selective filter, each cognitive radio node senses linear combinations of multiple channel information and reports them to the fusion center, where occupied channels are then decoded from the reports by using novel matrix completion and joint sparsity recovery algorithms. As a result, the number of reports sent from the CRs to the fusion center is significantly reduced. We propose two decoding approaches, one based on matrix completion and the other based on joint sparsity recovery, both of which allow exact recovery from incomplete reports. The numerical results validate the effectiveness and robustness of our approaches. In particular, in small-scale networks, the matrix completion approach achieves exact channel detection with a number of samples no more than 50% of the number of channels in the network, while joint sparsity recovery achieves similar performance in large-scale networks.

Wireless Tomography, Part III: Compressed Sensing for Ultra-wideband Signals by Peng Zhang, Robert C. Qiu. The abstract reads:

This is Part III of the wireless tomography three paper series.Wireless tomography is related to wireless communications in that it requires the channel recovery between different waveforms at transmit and receive, as well as multiple-input multiple-output (MIMO) communication system. According to the pulse propagation mechanisms of reflection and diffraction, ultra-wideband (UWB) waveforms suffer pulse distortion. Distorted pulses will overlap and therefore increases the sampling rate for accurate UWB channel recovery. Thanks to the recent progresses in sampling theory and radio propagation theory, we are able to propose a compressed sensing (CS) based UWB channel recovery method considering pulse distortion. The concept has been demonstrated through simulations. The sampling rate is as low as 2 Gsps, compared with the Nyquist rate of 50 Gsps. A CS based 2 × 2 MIMO communication system is also proposed and simulated. The communication problem is modeled as CS problem, and further reduce sampling rate required at the receiver.

Acceleration of Randomized Kaczmarz Method via the Johnson-Lindenstrauss Lemma by Yonina Eldar, and Deanna Needell. The abstract reads: 

The Kaczmarz method is an algorithm for finding the solution to an overdetermined system of linear equations Ax = b by iteratively projecting onto the solution spaces. The randomized version put forth by Strohmer and Vershynin yields provably exponential convergence in expectation, which for highly overdetermined systems even outperforms the conjugate gradient method. In this article we present a modified version of the randomized Kaczmarz method which at each iteration selects the optimal projection from a randomly chosen set, which in most cases significantly improves the convergence rate. We utilize a Johnson-Lindenstrauss dimension reduction technique to keep the runtime on the same order as the original randomized version, adding only extra preprocessing time. We present a series of empirical studies which demonstrate the remarkable acceleration in convergence to the solution using this modified approach.

Demonstration of real-time spectrum sensing for cognitive radio by Zhe Chen, Nan Guo, and Robert C. Qiu. The abstract reads:

The requirement for real-time processing indeed poses challenges on implementing spectrum sensing algorithms. Trade-off between the complexity and the effectiveness of spectrum sensing algorithms should be taken into consideration. In this paper, a fast Fourier transform based spectrum sensing algorithm, whose decision variable is independent of noise level, is introduced. A small form factor software defined radio development platform is employed to implement a spectrum sensing receiver with the proposed algorithm. To our best knowledge, it is the first time that real-time spectrum sensing on hardware platform with controllable primary user devices is demonstrated.

Airborne Radar STAP using Sparse Recovery of Clutter Spectrum by Ke Sun, Hao Zhang, Gang Li, Huadong Meng, Xiqin Wang. The abstract reads:

Space-time adaptive processing (STAP) is an effective tool for detecting a moving target in spaceborne or airborne radar systems. Statistical-based STAP methods generally need sufficient statistically independent and identically distributed (IID) training data to estimate the clutter characteristics. However, most actual clutter scenarios appear only locally stationary and lack sufficient IID training data. In this paper, by exploiting the intrinsic sparsity of the clutter distribution in the angle-Doppler domain, a new STAP algorithm called SR-STAP is proposed, which uses the technique of sparse recovery to estimate the clutter space-time spectrum. Joint sparse recovery with several training samples is also used to improve the estimation performance. Finally, an effective clutter covariance matrix (CCM) estimate and the corresponding STAP filter are designed based on the estimated clutter spectrum. Both the Mountaintop data and simulated experiments have illustrated the fast convergence rate of this approach. Moreover, SR-STAP is less dependent on prior knowledge, so it is more robust to the mismatch in the prior knowledge than knowledge-based STAP methods. Due to these advantages, SR-STAP has great potential for application in actual clutter scenarios.

A small Q&A with Rick Trebino, the inventor of FROG.

Following up on previous entries on the possibility of FROG being an instance of compressed sensing (which is still a question, part 1, part 2) I asked Rick Trebino, the inventor of FROG, some questions and he kindly responded to them. I initially started with:

Igor:

By the way, I stumbled on FROG about five years ago but did not get to make the parallel with compressed sensing only recently. If you have not had time to check compressive sensing, it really is a way of acquiring and reconstructing signals with a much lower number of samples than required by the Shannon-Nyquist theorem. This is possible because the signal is known in advance to be sparse. The main difference between FROG and CS so far seems that the measurement is nonlinear in FROG and that there is no stated assumption of sparsity of the underlying signal. With that in mind here are my set of dumb questions:

1- One of the reason I mentioned that FROG might be an instance of nonlinear compressed sensing revolves around the fact that you are reconstructing a pulse, which while it might be complex, is alone in a "sea" of nothing. Is that accurate? Are the pulses that you are recovering, signals that are "sparse" in time, i.e. the smallest pulse is really a pulse surrounded by no signal ?

Rick responded with:

We don't need to assume that the pulse is alone; the sea of zeroes confirms that it is.

I then asked:

2- Have you had any instances where your reconstruction is known to fail or does not yield accurate results ? Are those instance related to the laser pulse being "long", not sparse enough ?

Rick:

Yes. If the nonzero region of the trace is cut off, it often fails (but this seems reasonable, as key information is missing). And for very complex pulses in the presence of noise, it also can fail. When it does, disagreement between the measured and retrieved traces tells us this, and we know not to trust the result. This doesn't seem to be related to sparseness, however. There is, however, one interesting case perhaps related to sparseness, and that is the "ambiguity" of a pulse with well-separated frequencies, whose relative phases cannot be measured at all, even in the absence of noise; they have the same FROG traces, independent of the relative phases. Interestingly, alternative methods developed to measure such pulses also have this ambiguity.

Igor::

3- Once you get a FROG spectrogram, do you use all the data from the spectrogram to reconstruct the full signal ? have you ever toyed with the possibility of reconstructing the signals with a (random) subset of the elements of the spectrogram ?

Rick:

Yes, we always use all the data. A clever fellow named Craig Siders did develop a FROG algorithm that began by using only every eighth point. Then every fourth, etc., until the last few iterations, when he used all the data. This sped up the code considerably. But today's laptops are so fast that we haven't needed it. On the other hand, it might be worth reconsidering, as faster is always better! We have also used random subsets of datapoints to do a bootstrap computation of error bars, which worked very well.

Igor:

4- If I understand correctly GRENOUILLE is an hardware implementation of FROG. Is somebody selling that hardware ? in the affirmative, who is it ?

Rick:

Yes. I formed a company a few years ago (Swamp Optics, www.swampoptics.com), which has by now sold GRENOUILLEs to most ultrafast labs, and, as a result, has forced a whole generation of ultrafast scientists to use some utterly frivolous acronyms in their daily work and publications.

Rick also rightly pointed out the following:

But, in the meantime, I should mention that, at the moment and from what I understand of it (which isn't much), it seems to me that FROG may actually be the opposite of compressed sensing! The FROG trace actually contains much more data than is necessary to determine the pulse (an NxN array to determine N intensity points and N phase points). This is one its strengths, as it's easy to take all this data in a camera trace, and, more importantly, optics devices can often be difficult to set up and align, so systematic error can occur, and the redundancy in the trace serves as a check that that isn't occurring. The sea of zeroes is even more redundancy.

To what I responded with:

I realize that you are producing more data, however, your answer to question 3 seems to indicate that you can use less and that you can use a random set which would have some of the hallmarks of CS.

Thanks Rick.

Credit: NASA / JHUAPL / CIW. Earth and the Moon from much closer to the Sun. See those two bright dots? That's the double planet of Earth and the Moon. MESSENGER captured this view of its birthplace on May 6, 2010, during a search for vulcanoids, asteroids that are theorized to reside between Earth and the Sun. No vulcanoid has yet been discovered, but searches continue.

CS: Q&As and jobs, A job at Siemens.

Before we get to it, just a reminder that the LinkedIn Compressive Sensing Group now has 497 members. You could be its 500th! Moshiko Mishali (who is about to graduate, check his CV here) and I talked briefly about a job board around the specialties involved in Compressive Sensing. However I think the "market" is small for the moment and any job posts can be handled directly on this blog and the attendant Compressive Sensing Jobs page. There is also the possibilities for companies to post job positions directly on the LinkedIn Compressive Sensing Group. For students and other position seekers, I am sure it is in their best interest to be able to show some capabilities by responding professionally to the Q&As of the LinkedIn forum or to any public Q&A sites that are springing nowadays. As I mentioned to Suresh on Twitter, the reason these Q&As site spring up is that they are money makers for the people hosting or renting the servers on which these programs run. One way to do that is to provide recruiters with high quality leads ( people with high Karma).

Mariappan Nadar, a program Manager at 3D Interactive Processing at Siemens just let me know of this new opening in the field of Sparse Reconstruction (it will be added to the Compressive Sensing Jobs page shortly):

Research Scientist
Company Siemens Corporate Research
Division SCR - Siemens Corporate Research
Functional Area RD - Research & Development
Location NJ - Princeton
Req ID 90602
Job Type Regular
Job Time Full-Time
Experience Level Mid Level
Required Education Doctorate Degree
Required Travel 10%

Company Description

ABOUT SIEMENS CORPORATE RESEARCH:

Siemens Corporate Research (SCR), a division of Siemens Corporation, located in Princeton, New Jersey (USA) is Siemens’ largest research center outside of Europe. For more than thirty years, leading organizations in the private and public sectors have turned to the company for its expertise in breaking down barriers to innovation and delivering real business value. With more than 250 scientists, engineers, and technical experts, the company helps its customers and strategic partners grow their businesses in the fields of healthcare, automation, production, energy, industry, information and communications. SCR offers a stimulating research environment and rewarding career opportunities.

Siemens is an Equal Opportunity Employer encouraging diversity in the workplace.

Job Description



We have an immediate opening for a research scientist in the field of Computational Imaging, Image Science, Inverse Problems in Imaging with a focus on signal / image recovery and reconstruction. The candidate will have extensive knowledge and experience in Numerical methods, Optimization, Statistical Signal / Image recovery, Digital Image and Signal Processing. The ideal candidate will have a strong theoretical background, excellent oral and written communication skills, awareness of the state-of-the-art and the ability to realize the theory to provide working solutions for commercial, scientific or industrial applications.

Responsibilities:
- Research image and data analysis techniques to advance the state-of-the-art, including publication in top journals and conferences
- Apply image and data analysis methods to real world problems
- Quick prototyping, feasibility studies, specification and implementation of data analytics software product components
- Work with customers to understand algorithm requirements

Essential Skills and Qualifications:
- Ph.D. in Electrical Engineering, Computer Science, Applied Mathematics or related discipline
- 5-8 years of work experience in related field and successful demonstration of Key Responsibilities
- Proven ability to develop new research ideas and early developments to the level of a working system prototype
- Strong theoretical & practical background in Applied Mathematics, Optimization, Signal Processing, Statistical Image Models, Pattern Recognition and Machine Learning
- Good experience working in Medical Imaging domain. Knowledge in MRI physics and MRI signal processing, Parallel Imaging is a plus
- Ability to quickly prototype in Matlab/C/C++. GPU programming experience is a plus
- Outstanding written and verbal communication skills
- Excellent interpersonal skills and can do attitude
- Ability to work independently and prioritize work
- Strong collaboration skills and ability to thrive in a fast-paced environment
- Flexibility and adaptability to work in a growing, dynamic team

Siemens Corporate Research (SCR), a division of Siemens Corporation, is Siemens' largest research center outside of Europe. For more than thirty years, leading organizations in the private and public sectors have turned to the company for its expertise in breaking down barriers to innovation and delivering real business value. With more than 250 scientists, engineers, and technical experts, the company helps its customers and strategic partners grow their businesses in the fields of healthcare, automation, production, energy, industry, information and communications. SCR offers a stimulating research environment and rewarding career opportunities.

Siemens is an Equal Opportunity Employer encouraging diversity in the workplace.
EOE/AA/MFDV

Credit: One of Pedro's friend. According to him, that bridge in Laredo will be gone soon.

Q&A sites.

Everybody knows MathOverflow by now but two new sites have been showing up on my radar screen lately (Thanks Aleks)

Statistical Analysisis a proposed Q&A site for statistics, data analysis, data mining and data visualization.

And there is a new site MetaOptimize that features Q&A's about::

A community of data geeks interested in machine learning, natural language processing, artificial intelligence, text analysis, information retrieval, search, data mining, statistical modeling, and data visualization, as well as adjacent topics.

The latest questions related to some of the issues discussed here on Nuit Blanche include:

• What is the best introductory text on Random Matrix Theory?
• When should you prefer GraphLab over MapReduce? And vice-versa?

CS: Q&A with Esther Rodriguez-Villegas on a Compressive Sensing EEG

[I have updated this entry after some thoughts]

In Thursday's entry, I mentioned the paper by Amir Abdulghani, Alexander Casson and Esther Rodriguez-Villegas entitled Quantifying the Feasibility of Compressive Sensing in Portable Electroencephalography Systems where the authors look at an EEG compressive sensing system. Then, I stated the following:

....The result for 20 channels springs from applying a compressed sensing design such as the one shown above. The question I have is really how can we change this design entirely: For instance, instead of applying a simple \phi measurement to the signals after they have been amplified and digitized, what about providing some randomness in the reference voltage ? what about removing entirely both the Op-amps ?...

I had a small conversation with Esther Rodriguez-Villegas and here is her response to the question above republished with her permission (-as usual-)

Dear Igor,

Thanks for your email. We've heard of your blog before. It is very interesting.

....

On a different note we found the EEG discussion on your blog interesting. I personally don't think that the randomness in the reference voltage would work though. The latter would somehow be equivalent to "downsampling the signal with dither", or in different words, the randomness in the reference voltage would create a similar effect to the input noise already introduced by the amplifiers themselves and then I presume one would be downsampling. However I don't think this would be possible because the minimum sampling rate was determined to be what it is for different applications considering the existing amplifiers noise, so I doubt it would be viable to further reduce this sampling rate after adding a signal which, from the circuit point of view, would play a similar role to this noise. The other alternative of switching on and off the reference would not be a practical option either because of slew-rate limitations of the amplifiers, which could only be overcome by pumping otherwise unnecessary biasing currents.

At the same time, eliminating the amplifiers is not an option because they are needed to "adjust" the already very weak signal levels to the ones required by the A/D converters, and in some cases also act as filters for, for example, the offset drift introduced by the electrodes, as well as high frequency noise. One could argue that having a better converter to cope with an increased range may do the job, but the problem with that would be that converters themselves require considerable amount of power, and as the number of bits of resolution they provide increases they become much more power hungry (apart from considerably more difficult to design). Also, if one thinks of a system that ideally should be operated on small batteries which provide a very limited voltage, this on its own represents a limitation for the converter range. So in the end, in the context of a low power portable system, for the front end, having an amplifier followed by a lower resolution converter is going to be the best option as long as the blocks are intelligently designed and customised, which from the circuit designer perspective is not a simple issue at all.

Now, your overall suggestion is interesting because even if those two options are not possible, there may be alternative ones that are. Fundamentally, I would say that thinking of a system in which part of the processing which is now thought of at a digital level, is "transferred back" to the front end and carried out in the analog domain may potentially significantly reduce both, the "requirements" of the converter and also the overall power consumption of the approach. This is because analog can offer a massively better tradeoff in terms of computational complexity versus power than digital, as long as speed of the operations is not a major issue and we are not trying to deal with resolutions of more than about 10 bits. So as a conclusion, I would say that I definitely agree with you in the fact that we should "think out of the box" and make an effort to redefine the system. I would go further than that to say that most probably that "redefinition" should follow an approach in which part of the compression algorithm is implemented earlier on in the "system chain" possibly following an analog based approach.

Anyway, to this end, we have a paper under review at the moment showing the performance of a straightforward CS application to EEG, tailored to establish a baseline performance of the approach to aid future EEG designers to make system level decisions. From that paper I would say that in general better performance is needed, although it is left to the application specific designer to decide. Certainly however there is a lot of potential here for EEG-tailored system level oriented compressive sensing research.

Best regards,

Esther

I did not realize that the op-amp was also acting as a filter, this is good to know. From this description, it seems obvious that at some point one should investigate an electrode based solution. While roaming through the openEEG list, I was made aware of the fact that there are two types of electrodes : active and passive. The passive ones require that they be wetted with eye drops in order to make a good contact with the scalp. In case, they are not wetted, there seems to be an extreme sensitivity of the electrode to the environmental EMI coming from your everyday appliances. In that case, one could conceive the use of shielded electrodes. The active electrodes remove the need for this eye drop liquid agent but there is the danger of having a "live" electrode. With this in mind, one could probably think of the' early in the chain' comment that Esther suggests, whereby a very low voltage active electrode could provide some type of random modulation.

Since we are thinking outside the box and we are dealing with amplifiers (or their potential removal) there is also the possibility of extreme quantization of the signal. Work along those lines include that of Petros Boufounos and Richard Baraniuk in 1-Bit Compressive Sensing and that of Laurent Jacques, David Hammond and Jalal Fadili, as featured here.

Finally, with regards to Esther's other comment on the reference voltage, it seems that the concept of Garbage in, Garbage out does not really apply in compressive sensing when done right. I am making a particular reference to an early paper by Joel Tropp, Michael Wakin, Marco Duarte, Dror Baron, and Richard Baraniuk entitled Random Filters For Compressive Sampling And Reconstruction where one can read the following sentence:

At first glance, one might think this method would convert a signal into garbage.

As I said before, you don't often see that type of assessment in publications. I tried these random filters, and it worked for the limited case I computed.

Finally, to give some perspective with regards to low cost EEGs used in BCI-like systems, a current low cost commercially available Emotiv EEG system, with 14 electrodes, is limited by its battery capability of about 12 hours. It also uses passive electrodes and therefore liquid drops as the liquid needed to make good contact with the scalp. One can expect this liquid to evaporate over a 12 hour time period.

Thanks Esther for sharing your views!

Credit Photo: Emotiv, Emotiv Headset.

CS Community: Top Ten Questions You Wanted To Ask About Nuit Blanche But Were Afraid To Ask

I have increasingly interacted with some of you in person or by e-mail over the past two months. It's been great and I have enjoyed it very much. Through these conversations, I felt that there were common themes that I'd like to address here in a fake Q&A entitled: Top Ten Questions You Wanted To Ask About Nuit Blanche But Were Afraid To Ask.

10. Being Featured Here Seems to Produce Some Impact Beyond Your Field.

I heard through the grapevine, that at least one of you got a larger than normal amount of download of his paper after being featured here. wow. I have no proof but I also have had the impression that the blog may have brought about some discussions within papers. If this is the case, I am doubly impressed...Really... With people from such diverse backgrounds coming to the site, one would expect some type of acceleration in the use of compressed sensing.

9. Traffic Is Increasing

There are about 82 people reading this blog daily through an RSS feedreader and about 160 people coming daily to the site through search engines like Google or Yahoo. This is an increase of about 20 readers from the RSS feed and a average of 4000 hits every month on the site (three months in a row). I have noticed that when I link to smaller blogs that mention compressed sensing, they generally get a boost from 0 to 2 in the Pagerank system.

8. No, I Don't Spend All My Day Doing This.

In order for me to find relevant articles, I use a service called Watchthatpage. I have collected about two to three hundred pages that are being watched everyday through this service. If you put something new on your publication page, I am likely to see it but if I don't, you need to tell me "Hey Igor, there is something here....". If by the same token you could provide the name of your co-authors with a link to their personal webpages, it would be fantastic. By doing so, you will also help produce a de-facto Community. Also Nuit Blanche does not refer to my spending all night on the blog, rather that when traveling, jet lag helps in writing thoughtful posts in the middle of the night.

7. I Won't Tell.

I have seen sites that were not well protected (please check your chmod permissions) but I have no intent on linking to them or even using that information as the goal of this blog is to share information that people are willing to share.

6. A Webpage: What Is It Good For ?

I understand that putting something on the web maybe not seen important as most of you are not judged professionally on this effort. But if you do want your ideas to be read, implemented and make a difference beyond your field, then I urge you to make that paper (not a reference title) available on your site. At the very least, you should send a copy to Mark Davenport at the Rice Compressive Sensing Resources site.

5. Hosting is Possible But Not Recommended.

I'd rather not host a paper or a code (that is not mine) on my site but I understand that sometimes there is no other way to make it available.

4. Share It Because It's Fair Use.

I believe that my using figures and text of papers in these blog entries are fair use. I am pretty much convinced (and it looks like I am not the only person to think that) that one group doing compressed sensing has received less publicity and probably less acknowledgments from their work because they did not provide directly their papers on their websites. It's a shame.

3. Be Someone.

The corollary of item 4 is that people, especially students, need to have webpages as it directly impacts their ability to show off to their future employers and/or colleagues. Young researchers in France, Indonesia and Iran have webpages with their newer publications, I find it odd that in this day and age, some people in the U.S. still don't even have a web presence as it takes about fives minutes to set up one up on googlepages.

2. Sometimes I Just Don't Get It. Be Kind, Straighten Me Out.

If you feel I am not understanding or putting the wrong emphasis on issues you articulated in your paper. Please by all means mention it to me. There is a high probability that somebody has been, like me, misunderstanding what you meant. This is why I generally I ask for your permission to put our interaction on a blog entry. We all know that the rest of the crowd gets a deeper understanding from these types of teacher-student relationship. I have noticed that there is a mix of newcomers and people who have published on the subject coming to the site. Some of these newcomers, cannot for different reasons spend too much time in understanding the subject. The blog acts as a technology watch of some sorts to them and they want to get a sense that the subject is lively, i.e. that the community is still taking a stab at different questions of importance that sometimes can only be revealed by asking dumb questions.

1. If You Like It, Link To It.

If you like this blog, please take two seconds of your time and link to this blog at the following address:

http://nuit-blanche.blogspot.com/search/label/CS

with the title "Compressed Sensing Blog". Google does a very bad job at linking to this address. Instead it links to specific articles that are not wholly relevant sometimes. I would like to have the freedom of posting outside of compressed sensing every once in a while. If you use this address, only CS related issues will appear on your screen and I'll be free to talk about subjects such as technical issues in Space, Search and Rescue operations, Cognition and Cognition Deficit, Artificial Intelligence and Robots as I used to without boring you with these issues.

CS: Q&A on the Restricted Isometry Property for Compressed Sensing Recovery.

Since the Restricted Isometry Property of measurement matrices in Compressed Sensing is such a big deal (even though it is just a sufficient condition) and since the Structurally Random Matrices introduced earlier include a wide variety of previously studied measurement matrices, I went on and asked Thong Do the following question:

Are there any results stating that your structurally random matrices have the Restricted Isometry Property in general?

Thong Do kindly responded with the following:

... The issue of RIP of a random subset of rows of an orthonormal matrix (a generalization of Partial Fourier) was studied by M. Rudelson and R. Vershynin in the paper "On sparse reconstruction from Fourier and Gaussian measurements" [Note from Igor: Comment on that paper is here, also useful are the related slide presentations: Lecture 3: Random Fourier matrices and Commentary and Bibliography]. There is RIP for this family of matrices but it is not as good as RIP of Gaussian matrices. In other words, if we use this family of matrices for sensing, it would require O(Klog^4(n)) rather than O(Klog(n)) measurements for the so called uniformly exact recovery (as in the sense guaranteed by RIP). If we only want non-uniformly exact recovery, then Candes showed in his paper "Sparsity and Incoherence in compressive sampling" that it only requires to have O(Klog(n)) measurements. In other words, O(Klog(n)) of Gaussian measurements guarantees uniform exact recovery while the same number of measurements from a random subset of rows of an orthonormal matrix will only guarantee a non-uniform exact recovery. So what are the uniform and nonuniform businesses ? Roughly speaking, it's like to say a Gaussian matrix would work for all signals (with high probability) while a Partial Fourier only work for a GIVEN signal (with high probability).

I'm sure that SRM has RIP as good as a subset of rows of an orthonormal matrix but have not been sure if SRM's is better and how much better...

I also am receiving other questions that are generally not answered straightforwardly in the papers I have read. I wish they were addressed at some basic level. Here are some:

1) if y= phi x where x is the sparse signal and phi the sensing matrix size k*N; k less than N; do the columns of phi need to be normalized to 1 for RIP to imply perfect recovery?

2) In some papers y= Ux = phi psi x is the formulation (x is sparse). In this case the RIP is applicable for U right? not just for phi?

I think these questions can be clarified by reading Emmanuel Candes and Justin Romberg's paper entitled Sparsity and Incoherence in Compressive Sampling.

However, the short answer to the first question is yes some normalization is in order otherwise bounds for some of the inequalities for the concentration of measure will be off. The short answer to the second question is yes. The short answer to the third question is: the reason you think you need phi to have the RIP is because in this case psi is the identity. Eventually only U counts, phi then only needs to be incoherent with psi.

With regards to checking the RIP of a specific matrix, here is another question:

If i want to check the Restricted Isometry property for measurement matrix F, it should satisfy for all S-sparse vectors x, the following relationship,



In the paper of Candes Decoding by Linear Programming,its written that if above condition is satisfied, all eigenvalues of (F*F),where F* is the Hermitian of F,should lie between and .

I have a question regarding eigenvalues of F*F.I have checked there may exist F which satsifies the above Restricted Isometry for all S sparse vectors but still the eigenvalues of F*F may not lie between and ?

then an example is given:

A simple example,length of sparse vector=N=5
number of measured samples=M=4
Sparsity=S=2

Creating Partial fourier matrix(without randomizing the rows) and normalizing its columns
F=dftmtx(N);
F=normalize(F(1:M,:));
I have sparse vector x
x=[0 0 0 0.6820 0.5253];

The RIP condition



is satisfied for delta=0.11()

But if we see the eigen values of matrix F*F are[0.75,1.25] which does not lie between . Hence even if for some sparse vector x,the RIP condition is satisfied but it doesnt imply about the bounds on eigenvalues.

The short answer is: the delta you computed is for one sparse vector, not for all sparse vectors. In turn, the eigenvalues of the matrix still give a lower bound for the RIP constant.

But....but how do you find the RIP constant ? well you need to try all the sparse vectors, this is why this is a combinatorial search. This is why the possibility of finding this RIP constant using Sparse PCA raises some interest. This is also why, if it is indeed NP-hard, it needs to be understood that the RIP is only a sufficient condition, that there are other constructions (Combining Geometry And Combinatorics: A Unified Approach to Sparse Signal Recovery by Radu Berinde, Anna Gilbert, Piotr Indyk, Howard Karloff and Martin Strauss) that are not RIP(2) but RIP(1) yet allow for full recovery. In my opinion, the work of Jared Tanner (Phase Transition Phenomenon in Sparse Approximation) also point to other potential constructions that work.

If any of these answers are wrong, please go ahead and comment.

Credit: NASA/JPL/University of Arizona, Phoenix Lander as seen by the Hirise Camera on-board the orbiting Mars Reconnaissance Observer after landing.

CS: Q&A, Noise reduction through CS, reconstruction from undersampled k-t space, L1-minimization methods for Hamilton–Jacobi equations.

In a previous entry, I mentioned the work ofAlexandre d'Aspremont, Laurent El Ghaoui, Michael I. Jordan, Gert Lanckriet featured in A Direct Formulation for Sparse PCA Using Semidefinite Programming. In one of the slide (27) I put on the blog one can read:

"....Upper bounds for sparse PCA prove deterministically and with polynomial complexity that a finite dimensional matrix satisfies the restricted isometry condition...."

I had not paid real attention to that part of the slide but Jort Gemmeke did and asked the following question in the comment section:

I have trouble understanding the conclusion on the sparse PCA slide: what does it mean that "a finite dimensional matrix" satisfies the RIP property? Could you give an interpretation?"

Alexandre kindly responded offline with:

I mean that sparse PCA produces upper bounds on the restricted isometry constant, hence can potentially prove that a given finite dimensional matrix follows the RIP instead of relying on asymptotic results.

That certainly clears it up. Thanks Alexandre and Jort.

While on their sites, I found the following preprints/talks of relevance to Compressed Sensing:

Jort Gemmeke and Bert Cranen released Noise reduction through Compressed Sensing. The abstract reads:

We present an exemplar-based method for noise reduction using missing data imputation: A noise-corrupted word is sparsely represented in an over-complete basis of exemplar (clean) speech signals using only the uncorrupted time-frequency elements of the word. Prior to recognition the parts of the spectrogram dominated by noise are replaced by clean speech estimates obtained by projecting the sparse representation in the basis. Since at low SNRs individual frames may contain few, if any, uncorrupted coefficients, the method tries to exploit all reliable information that is available in a word-length time window. We study the effectiveness of this approach on the Interspeech 2008 Consonant Challenge (VCV) data as well as on AURORA-2 data. Using oracle masks, we obtain obtain accuracies of 36-44% on the VCV data. On AURORA-2 we obtain an accuracy of 91% at SNR -5 dB, compared to 61% using a conventional frame-based approach, clearly illustrating the great potential of the method.

This is outstanding, here is what I take away from this paper:

Experiments on AURORA-2 using an oracle mask, however, also clearly show the potential of the presented method: A recognition accuracy of 91% at SNR = -5 dB is obtained, an increase of 30% absolute over a state-of the art missing data speech recognizer using frame by frame imputation. This shows that even at very low SNRs enough information about the speech signal may be preserved to successfully perform imputation solely on the basis of reliable time frequency cells provided enough time-context is used.

State dependent oracle masks for improved dynamical features by Jort Gemmeke and Bert Cranen. The abstract reads:

Using the AURORA-2 digit recognition task, we show that recognition accuracies obtained with classical, SNR based oracle masks can be substantially improved by using a state dependent mask estimation technique.

Classification on incomplete data: imputation is optional by Jort Gemmeke. The abstract reads:

We present a non-parametric technique capable of performing classification directly on incomplete data, optionally performing imputation. The technique works by sparsely representing the available data in a basis of example data. Experiments on a spoken digit classification task show significant improvement over a baseline missing-data classifier.

Noise robust digit recognition using sparse representations by Jort Gemmeke and Bert Cranen. The abstract reads:

Despite the use of noise robustness techniques, automatic speech recognition (ASR) systems make many more recognition errors than humans, especially in very noisy circumstances. We argue that this inferior recognition performance is largely due to the fact that in ASR speech is typically processed on a frame by-frame basis preventing the redundancy in the speech signal to be optimally exploited. We present a novel non-parametric classification method that can handle missing data while simultaneously exploiting the dependencies between the reliable features in an entire word. We compare the new method with a state-of-the-art HMM-based speech decoder in which missing data are imputed on a frame-by-frame basis. Both methods are tested on a single digit recognition task (based on AURORA-2 data) using an oracle and an estimated harmonicity mask. We show that at an SNR of -5 dB using the reliable features of an entire word allows an accuracy of 91% (using mel-log-energy features in combination with an oracle mask), while a conventional frame-based approach achieves only 61%. Results obtained with the harmonicity mask suggest that this specific mask estimation technique is simply unable to deliver sufficient reliable features for acceptable recognition rates at these low SNRs.

Accelerating dynamic spiral MRI by algebraic reconstruction from undersampled k-t space by
T. Shin, J.F. Nielsen, Krishna S. Nayak. The abstract reads:

The temporal resolution of dynamic magnetic resonance imaging (MRI) can be increased by sampling a fraction of k-space in an interleaved fashion, which introduces spatial and temporal aliasing. We describe algebraically and graphically the aliasing process caused by dynamic undersampled spiral imaging within 3-D xyf space (the Fourier transform of k_x, k_y, t space) and formulate the unaliasing problem as a set of independent linear inversions. Since each linear system is numerically underdetermined, the use of prior knowledge in the form of bounded support regions is proposed. To overcome the excessive memory requirements for handling large matrices, a fast implementation of the conjugate gradient (CG) method is used. Numerical simulation and in vivo experiments using spiral twofold undersampling demonstrate reduced motion artifacts and the improved depiction of fine cardiac structures. The achieved reduction of motion artifacts and motion blur is comparable to simple filtering, which is computationally more efficient, while the proposed algebraic framework offers greater flexibility to incorporate additional algebraic acceleration techniques and to handle arbitrary sampling schemes.

Of related interest, there is: Accelerated spiral Fourier velocity encoded imaging by João Luiz Azevedo de Carvalho, Krishna S. Nayak.

and finally, L1-minimization methods for Hamilton–Jacobi equations: the one-dimensional case by Jean-Luc Guermond, Bojan Popov. The abstract reads:

A new approximation technique based on L1-minimization is introduced. It is proven that the approximate solution converges to the viscosity solution in the case of one-dimensional stationary Hamilton–Jacobi equation with convex Hamiltonian.

Credit: NASA/JPL/Space Science Institute, Daphnis and Prometheus, photo taken by Cassini five weeks ago.