CS: Seismic sampling, Compressive Sensing for MIMO Radar

Felix Hermann has two new presentations out on the work performed at his lab at UBC:

• Beating Nyquist by randomized sampling
• Compressive seismic imaging with simultaneous acquisition

There is also a new version of A fast algorithm for computing minimal-norm solutions to underdetermined systems of linear equations by Mark Tygert.

Finally, I just found this paper on arxiv: Compressive Sensing for MIMO Radar by Yao Yu, Athina Petropulu, H. Vincent Poor. The abstract reads:

Multiple-input multiple-output (MIMO) radar systems have been shown to achieve superior resolution as compared to traditional radar systems with the same number of transmit and receive antennas. This paper considers a distributed MIMO radar scenario, in which each transmit element is a node in a wireless network, and investigates the use of compressive sampling for direction-of-arrival (DOA) estimation. According to the theory of compressive sampling, a signal that is sparse in some domain can be recovered based on far fewer samples than required by the Nyquist sampling theorem. The DOA of targets form a sparse vector in the angle space, and therefore, compressive sampling can be applied for DOA estimation. The proposed approach achieves the superior resolution of MIMO radar with far fewer samples than other approaches. This is particularly useful in a distributed scenario, in which the results at each receive node need to be transmitted to a fusion center for further processing.

Compressed beamforming

 Compressed beamforming by Xenaki, Angeliki, Peter Gerstoft, and Klaus Mosegaard.

Sound source localization with sensor arrays involves the estimation of the direction-of-arrival (DOA) from a limited number of observations. Compressive sensing (CS) is a method for solving such underdetermined problems, which achieves simultaneously sparsity, thus super-resolution, and computational speed. We formulate the DOA estimation problem in the CS framework and show that CS has superior performance compared to traditional DOA estimation methods. A bias and resolution analysis is performed to indicate the limitations of CS. We show that the bias is related to the beampattern, thus can be predicted. To demonstrate the super-resolution capabilities and the robustness of CS, the method is applied to experimental data from ocean acoustic measurements for source tracking with single-snapshot data.

Of interest: A unified theory of microseisms and hum, James Traer, Peter Gerstoft

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

Thesis: Compressive Power Spectral Analysis by Dyonisius Ariananda

Compressive Power Spectral Analysis by Dyonisius Ariananda

At the heart of digital signal processing (DSP) are the sampling and quantization processes, which convert analog signals into discrete samples and which are implemented in the form of analog to digital converters (ADCs). In some recent applications, there is an increased demand for DSP applications to process signals having a very wide bandwidth. For such signals, the minimum allowable sampling rate is also very high and this has put a very high demand on the ADCs in terms of power consumption. Recently, the emergence of compressive sampling (CS) has offered a solution that allows us to reconstruct the original signal from samples collected from a sampling device operating at sub-Nyquist rate. The application of CS usually involves applying an additional constraint such as a sparsity constraint on the original signal. However, there are also applications where the signal to deal with has a high bandwidth (and thus sub-Nyquist rate sampling is still important) but where only the second-order statistics (instead of the original signal) are required to be reconstructed. In the latter case, depending on the characteristics of the signals, it might be possible to reconstruct the second-order statistics of the received analog signal from its sub-Nyquist rate samples without applying any additional constraints on the original signals. This idea is the key starting point of this thesis.

We first focus on time-domain wide-sense stationary (WSS) signals and introduce a method for reconstructing their power spectrum from their sub-Nyquist rate samples without requiring the signal or the power spectrum to be sparse. Our method is examined both in the time- and frequency-domain and the solution is computed using a simple least-squares (LS) approach, which produces a solution if the rank condition of the resulting system matrix is satisfied. To satisfy this rank condition, two options of sampling design are proposed, one of which is the so-called multi-coset sampling. It is show in this thesis that any of the so-called sparse ruler can produce a multi-coset sampling design that guarantees the full rank condition of the system matrix, and thus the optimal compression is achieved by a minimal sparse ruler.

While the approach in the previous paragraph is related to time-domain signals, we could extend the discussion about the power spectrum reconstruction from sub-Nyquist rate samples in the context of the spatial-domain signal, which is defined as a sequence of outputs of the antennas in the antenna array at a particular time instant. Given the compressed spatial domain signals, which are obtained from the output of a uniform linear array (ULA) with some antennas turned off, of particular interest is to reconstruct the angular power spectrum, from which the direction of arrival (DOA) of the sources can generally be located. In this thesis, a method to estimate the angular power spectrum and the DOA of possibly fully correlated sources based on second-order statistics of the compressed spatial-domain signals is proposed by employing a so-called dynamic array which is built upon the so-called underlying ULA. In this method, we present the spatial correlation matrices of the output of the dynamic active antenna arrays at all time slots as a linear function of the spatial correlation matrix of the entire underlying uniform array and we solve for this last correlation matrix using LS. The required theoretical condition to ensure the full column rank condition of the system matrix is formulated and designs are proposed to satisfy this condition.

Next, we consider both spatio-angular and time-frequency domains and propose a compressive periodogram reconstruction method as our next contribution. We introduce the multibin model, where the entire band is divided into equal-size bins such that the spectra at two frequencies or angles, whose distance is at least equal to the bin size, are uncorrelated. This model results in a circulant structure in the so-called coset correlation matrix, which enables us to introduce a strong compression. We propose the sampling patterns based on a circular sparse ruler to guarantee the full column rank condition of the system matrix and to allow the LS reconstruction of the periodogram. We also provide a method for the case when the bin size is reduced such that the spectra at two frequencies or angles, whose distance is larger than the bin size, can still be correlated.

To combine frequency and DOA processing, we also introduce a compressive two-dimensional (2D) frequency- and angular-domain power spectrum reconstruction for multiple uncorrelated time-domain WSS signals received from different sources by a linear array of antennas. We perform spatial-domain compression by deactivating some antennas in an underlying ULA and time-domain compression by multi-coset sampling.

Finally, we propose a compressive cyclic spectrum reconstruction approach for wide-sense cyclostationary (WSCS) signals, where we consider sub-Nyquist rate samples produced by non-uniform sampling. This method is proposed after first observing that the block Toeplitz structure emerges in theWSCS signal correlation matrix. This structure is exploited to solve the WSCS signal correlation matrix by LS. The condition for the system matrix to have full column rank is provided and some possible non-uniform sampling designs to satisfy this full column rank condition are presented.

Based on all the works that have been done, we have found that focusing on reconstructing the statistical measure of the received signals has significantly relax the sampling requirements and the constraints on both the statistics and the signals themselves. Hence, we would like to conclude that, for given tasks of applications in hand, we should ask ourselves whether statistical measure reconstruction is sufficient since the answer for this question will likely to determine how we should collect the data from the observed phenomena. This underlines the importance of awareness on what kind of information is necessary and sufficient for the tasks in hand before conducting the sensing/sampling process.

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

CS: Bob's adventures, Compressed Sensing based Method for ECG Compression, two theses and a postdoc

Bob's excellent adventures is featured on his blog and he has summarized everything in an arxiv paper entitled A Study on Sparse Vector Distributions and Recovery from Compressed Sensing by Bob L. Sturm. The abstract reads:

I empirically investigate the variability of several recovery algorithms on the distribution underlying the sparse vector sensed by a random matrix. a dependence that has been noted before, but, to my knowledge, not thoroughly investigated. I find that $\ell_1$-minimization \cite{Chen1998} and tuned two-stage thresholding \cite{Maleki2010} (subspace pursuit \cite{Dai2009} without the use of a sparsity oracle) are the most robust to changes in the sparse vector distribution; but they are outperformed to a large degree by greedy methods, such as orthogonal matching pursuit \cite{Pati1993} for sparse vectors distributed Normal and Laplacian. I also find that selecting the best solution from those produced by several recovery algorithms can significantly increase the probability of exact recovery.

Eric Trammel les us know on Twitter of a new paper and code in  Video Compressed Sensing with Multihypothesis by Eric Tramel and James E. Fowler. The abstract reads:

The compressed-sensing recovery of video sequences driven by multihypothesis predictions is considered. Specifically, multihypothesis predictions of the current frame are used to generate a residual in the domain of the compressed-sensing random projections. This residual

being typically more compressible than the original frame leads to improved reconstruction quality. To appropriately weight the hypothesis predictions, a Tikhonov regularization to an ill-posed least-squares optimization is proposed. This method is shown to outperform both recovery of the frame independently of the others as well as recovery based on single-hypothesis prediction.

The attendant code is here.

Sergey wonders about L1, robust statistics and compressed sensing

Thibault Reveyrand has a presentation in french entitled: Mise en œuvre de nouveaux concepts d’´echantillonnage pour la reception RF ultra-large bande

Over the week-end, I found one paper and two theses:

Compressed Sensing based Method for ECG Compression by Luisa F. Polania, Rafael E. Carrillo, Manuel Blanco-Velasco and Kenneth E. Barner. The abstract reads:

Compressive sensing (CS) is a new approach for the acquisition and recovery of sparse signals that enables sampling rates significantly below the classical Nyquist rate. Based on the fact that electrocardiogram (ECG) signals can be approximated by a linear combination of a few coefficients taken from a Wavelet basis, we propose a compressed sensing-based approach for ECG signal compression. ECG signals generally show redundancy between adjacent heartbeats due to its quasi-periodic structure. We show that this redundancy implies a high fraction of common support between consecutive heartbeats. The contribution of this paper lies in the use of distributed compressed sensing to exploit the common support between samples of jointly sparse adjacent beats. Simulation results suggest that compressed sensing should be considered as a plausible methodology for ECG compression.

Yaniv Plan's thesis Compressed sensing, sparse approximation, and low-rank matrix estimation. The abstract reads;

The importance of sparse signal structures has been recognized in a plethora of applications ranging from medical imaging to group disease testing to radar technology. It has been shown in practice that various signals of interest may be (approximately) sparsely modeled, and that sparse modeling is often beneficial, or even indispensable to signal recovery. Alongside an increase in applications, a rich theory of sparse and compressible signal recovery has recently been developed under the names compressed sensing (CS) and sparse approximation (SA). This revolutionary research has demonstrated that many signals can be recovered from severely undersampled measurements by taking advantage of their inherent low-dimensional structure. More recently, an offshoot of CS and SA has been a focus of research on other low-dimensional signal structures such as matrices of low rank. Low-rank matrix recovery (LRMR) is demonstrating a rapidly growing array of important applications such as quantum state tomography, triangulation from incomplete distance measurements, recommender systems (e.g., the Netflix problem), and system identification and control. In this dissertation, we examine CS, SA, and LRMR from a theoretical perspective. We consider a variety of different measurement and signal models, both random and deterministic, and mainly ask two questions. How many measurements are necessary? How large is the recovery error? We give theoretical lower bounds for both of these questions, including oracle and minimax lower bounds for the error. However, the main emphasis of the thesis is to demonstrate the efficacy of convex optimization---in particular l1 and nuclear-norm minimization based programs---in CS, SA, and LRMR. We derive upper bounds for the number of measurements required and the error derived by convex optimization, which in many cases match the lower bounds up to constant or logarithmic factors. The majority of these results do not require the restricted isometry property (RIP), a ubiquitous condition in the literature.

Yao Yu's Colocated MIMO radar using compressive sensing. The abstract reads:

We propose the use of compressive sensing (CS) in the context of a multi-input multioutput (MIMO) radar system that is implemented by a small scale network. Each receive node compressively samples the incoming signal, and forwards a small number of samples to a fusion center. At the fusion center, all received data are jointly processed to extract information on the potential targets via the CS approach. Since CS-based MIMO radar would require many fewer measurements than conventional MIMO radar for reliable target detection, there would be power savings during the data transmission to the fusion center, which would prolong the life of the wireless network. First, we propose a direction of arrival (DOA)-Doppler estimation approach. Assuming that the targets are sparsely located in the DOA-Doppler space, based on the samples forwarded by the receive nodes, the fusion center formulates an ℓ1-optimization problem, the solution of which yields the target DOA-Doppler information. The proposed approach achieves the superior resolution of MIMO radar with far fewer samples than required by conventional approaches. Second, we propose the use of step frequency to CS-based MIMO radar, which enables high range resolution, while transmitting narrowband pulses. For slowly moving targets, a novel approach is proposed that achieves significant complexity reduction by successively estimating angle-range and Doppler in a decoupled fashion and by employing initial estimates to further reduce the search space. Numerical results show that the achieved complexity reduction does not hurt resolution. Finally, we investigate optimal designs for the measurement matrix that is used to linearly compress the received signal. One optimality criterion amounts to decorrelating the bases that span the sparse space of the incoming signal and simultaneously enhancing signal-to-interference ratio (SIR). Another criterion targets SIR improvement only. It is shown via simulations that, in certain cases, the measurement matrices obtained based on the aforementioned criteria can improve detection accuracy as compared to the typically used Gaussian random measurement matrix.

Also I found this position:

Postdoctoral Positions in Wireless Communications / Media Security
DESCRIPTION
The Signal Processing in Communications Group (GPSC, www.gts.tsc.uvigo.es/gpsc), headed by Prof. Fernando Pérez-González and affiliated using the Department of Signal Concept and Communications at University of Vigo, Spain, invites applications for postdoctoral positions within the fields of wireless communications and multimedia safety. The selected candidates will join GPSC to investigate fundamentals and algorithm design/evaluation for communication, sensor networks and information forensics. Places of particular curiosity contain:
* Sensor networks
* Cognitive Radio
* Watermarking
* Compressed Sensing
GPSC is shaped by six faculty members, MSc and PhD pupils, and postdocs, and participates in many study jobs funded by the European Commission and the Spanish Authorities. Among these, the COMONSENS project (www.comonsens.org), led at University of Vigo by Prof. Roberto López-Valcarce, integrates investigators from 10 distinct top rated investigation institutions in Spain. GPSC members also actively collaborate together with the Galician R&D Center in Advanced Telecommunications (GRADIANT, www.gradiant.org) in diverse contracts with ICT companies. Thus, the selected candidates will enjoy unique opportunities to participate in exciting analysis assignments with both industry and academia.
DESIRABLE BACKGROUND
* A Ph.D. degree in Electrical Engineering is required.
* Applications from candidates with three or more years of postdoctoral experience will be given preference.
* Knowledge and experience in sensor networks, cognitive radio, watermarking & data hiding algorithms, multimedia forensics and/or compressed sensing
* Good verbal and written skills in English are required
* Strong publications in international conferences and journals in the area of communications
* Postdoctoral experience in a recognized group with expertise within the field is a plus
* Experience in the organization, management and training of technical staff/students is a plus
* Communication, computing and interpersonal skills are important
* Capacity to work both independently and within a team
CONTRACT CONDITIONS
The initial appointment will be for one year, with annual renewaldependent on performance. Expected start date is April 2011. Successful applicants will be offered a yearly gross salary from the range of 33,000 -40,000 €, as well as health benefits.
APPLICATIONS
Interested candidates may apply to Prof. Roberto López-Valcarce(valcarce[ at ]gts.uvigo.es). Applications should incorporate electronic copies of the following:
* A detailed Curriculum Vitae. (*Please incorporate your e-mail address and a recent picture.)
* A cover letter addressing the specified job qualifications.
* A letter of recommendation by a senior Professor/Researcher.
* A copy of the publication deemed as best representative of the candidate’s creative study.
Priority consideration will be given to applications received by late March, 2011.
Applications will be accepted until position is filled.
MORE INFO:
Prof. Roberto López?Valcarce
Departamento de Teoría de la Señal y Comunicaciones
ETSET. University of Vigo, 36310 Vigo. Spain
Phone: +34 986 818659,
e?mail: valcarce[ at ]gts.uvigo.es

Credit: NASA/JPL/University of Arizona

Icy Craters on Mars
ESP_016954_2245

Newly formed impact craters have been discovered on Mars over the past several years. When craters form over dusty regions the impact blast blows the bright dust off the terrain over a wide area, leaving a dark spot.

CS; CS in infinite dimensional space, Ditributed Bearing Estimation via matrix Completion, Optimal incorporation of sparsity information

If you thought some of the techniques used to reconstruct signals took long, you've never tried "infinite dimensional convex optimization" :-). This is the subject of today's first paper: Compressive Sampling in Infinite Dimensions by Anders C. Hansen. The abstract reads;

We generalize the theory of Compressive Sampling in Cn to infinite dimensional Hilbert spaces. The typical O(log(n)) estimates (where n is the dimension of the space) are manipulated to fit an infinite dimensional framework.

Looking at the other interest of the author, I wonder aloud if there is a connection between the computation pseudospectra and the RIP/NullSpace conditons ? For more information on computing pseudospectra of rectangular matrices, one can check Eigenvalues and Pseudospectra of rectangular matrices by Thomas Wright and L. Nick Trefethen. You'd think there is a connection and that theorem 2 would help (since multiplying a matrix with a class of sparse vector is really about reducing the number of columns of that matrix). There is also a connection between DOA and pseudospectra and DOA has been the subject of several papers mentioned here before.


Volkan Cevher let me know of a new paper Ditributed Bearing Estimation via matrix Completion by Andrew Waters and Volkan Cevher. The abstract reads:

We consider bearing estimation of multiple narrow-band plane waves impinging on an array of sensors. For this problem, bearing estimation algorithms such as minimum variance distortionless response (MVDR), multiple signal classification, and maximum likelihood generally require the array covariance matrix as sufficient statistics. Interestingly, the rank of the array covariance matrix is approximately equal to the number of the sources, which is typically much smaller than the number of sensors in many practical scenarios. In these scenarios, the covariance matrix is low-rank and can be estimated via matrix completion from only a small subset of its entries. We propose a distributed matrix completion framework to drastically reduce the inter-sensor communication in a network while still achieving near-optimal bearing estimation accuracy. Using recent results in noisy matrix completion, we provide sampling bounds and show how the additive noise at the sensor observations affects the reconstruction performance. We demonstrate via simulations that our approach sports desirable tradeoffs between communication costs and bearing estimation accuracy.

Finally, today's arxiv new addtion: Optimal incorporation of sparsity information by weighted $L_1$ optimization by Toshiyuki Tanaka and Jack Raymond. The abstract reads:

Compressed sensing of sparse sources can be improved by incorporating prior knowledge of the source. In this paper we demonstrate a method for optimal selection of weights in weighted $L_1$ norm minimization for a noiseless reconstruction model, and show the improvements in compression that can be achieved.

Feedbacks on Adaptivity in Compressive Sensing, a post peer review of SL0 and Pre-Peer Review Publishing

In response to Adaptive Compressive Sensing and a short Q&A with Mark Davenport, Eric Price commented

It's really quite simple: let the "error" of an algorithm be the squared ratio of noise in the output to noise in the input.

• Non-adaptively, the error is at least (k log (n/k)) / m and this is achievable. (standard)
• Adaptively, the error can be as low as (k log log (n/k))/m. (I believe Jarvis gets this for some range of parameters; our algorithm gets it everywhere.)
• Adaptively, the error can't be lower than k/m. (this paper.) 

 There's no contention in the results, only in whether an exponential improvement in the dependence on n "doesn't help" or is "fundamentally better."

The reference Eric is talking about is: On the Power of Adaptivity in Sparse Recovery by Piotr Indyk, Eric Price, David Woodruff.(featured here). Mark Davenport replied with: 

Eric,
I agree there is no contention between the results you mention and the claims in our paper, but we're not just arguing semantics here.
It's a little more than that -- if the SNR is just a little bit higher than the "worst-case" level, then the error can be as low as k^2/(nm). That's a vast improvement over k/m (assuming that k << n). So there is seemingly the potential for a vast improvement, way beyond just removing the log factor.

None of the results you mention are aiming at this level of improvement, because it is indeed impossible to obtain in general (i.e, for all input signals).

In the current review process, this very interesting discussion and insight would be hidden from us, how is Science served ? Let us pile on this thing a little further, in A Post Peer Review of SL0, an anonymous commenter made the thoughtful comment:

SL0 is too sensitive to noise. This limits its applications to many fields, like gene expression, network mining, sparse representation of natural signals (biosignals, etc), DOA estimation, ....

We should not over-praise algorithms behaving better in noiseless scenarios. After all, sparsity based signal processing/machine learning covers many fields. And over-praising such an algorithm may mislead your readers with various background/applications.

I emphasized the first sentence because there is something perverse at play and it makes my blood literally  boil. After reading the only comment of that thread:

Regarding sensitivity of SL0 to noise, what about Robust SL0 , it is less sensitive to noise compared to the original SL0?

I wrote to one of the author, Massoud Babaie-Zadeh, one of the author of SL0 and he tells me they even had a better implementation of this Robust SL0 dealing with the projection a little differently, but that got rejected in the peer review process and is therefore not implemented in SL0. So yes, anonymous is right, SL0 does not work well with noise because the peer-review process does not let it. How are "gene expression, network mining, sparse representation of natural signals (biosignals, etc), DOA estimation, ...." held back since 2009 because of peer review ? How is Science served ? 

Which leads us to these interesting and thoughtful comments on the subject of pre-publication peer review, I have received many comments on how To Serve Science in just a few hours this is certainly an issue that is currently not addressed effectively, here are the comments:

Serguey Ten started with:

This arxiv-thing could be even bigger than peer-review - the article would have "tail" of question about difficult places from novices in the area, explanations from author/experts, reports on 3rd party implementations - all blurring the edges between paper, book on the subject and textbook. Would be great!

Then Laurent Duval added:

For ONLY one additional reading on the topic, I suggest Opinion 101: The Newly launched Journal Rejecta Mathematica IS a JOKE (but so are all math journals!) by Doron Zeilberger: "Let me conclude with a revolutionary proposal to save paper, and disk-space, by making all math journals virtual. Only keep the arxiv, but for each paper, just mention what journal it got accepted to."

I also add the June 2011 issue of the IT Society newsletter where A. Ephremides (The Historian’s Column, page 7) recalls that, half a century ago "The papers were FIRST published in the Transactions and THEN they were presented at the Symposium!! That is a total reversal of what we do today. The distinct advantage of this arrangement was that the audience had the benefit of studying the papers carefully ahead of time, which enabled an in-depth discussion after the presentation. Not a bad idea!. This would be a "revolution" indeed, in its radical sense: going back to the same place, althought a bit later.

Don't you think a conference (why not video/virtual?) would be a great post-peer review place?

Then Thomas Arildsen added

ArXiv is already great, IMO because it's a great place to monitor new research appearing as opposed to trying to keep track of all relevant journals in the field. Plus, the latter has quite a delay. This extra layer would be a huge leap forward. I can't help thinking; why doesn't "somebody" do that.

then Petros Boufousnos provided more to the idea:

This is in some view very similar to the concept of "working paper" in economics and other fields. From what I understand (and I can't say I understand it completely) economists publish a "working paper" in the community, which is circulated, discussed, cited, presented in conferences etc. The paper is in some sense a living document and keeps changing as new comments/suggestions pile in. This is in some sense what Igor calls "post-publication peer review." Once the paper is in a final good state and accepted by the community, a journal publishes it, which is the official validation of the paper. I am not sure about two things: a) If the journal actively contacts the author and picks up the paper or the author submits to the journal and b) how intensive is the blind peer review process by the journal's editorial process once the validation in the community exists for the working paper.

This is a model that I think works quite well, especially for a slow-moving field such as economics. In our fields, arXiv can definitely serve this purpose. A meta-service might be necessary for posting comments/feedback, although this could in principle be embedded in arXiv. The field of economics shows that this is not even necessary since e-mail, conferences, blogs etc. can play that role. Still, a more formal comment/review/discussion process would be nice. (BTW, integrating google scholar citations with Google+ and maybe blogger would be a great platform for this... One Google to rule us all!)

What is necessary, however, is that the community understands and accepts this process. This might be harder than it seems. We have been having arXiv for so long now, posting papers and citing then, and still people don't accept it. For example, a recent paper I submitted to a conference relied and cited on results in my Universal Scalar Quantization paper on arXiv, before it had been accepted by Trans. IT. One of the comments of one reviewer was "The paper depends heavily on an unreviewed open-source published document [...] I cannot trust the cited work is correct so it must be reviewed before it can be used for a serious paper [...]" and proceeded to trash the remaining of the submission. Thankfully the remaining reviewers saw the value of the paper and accepted it. However, this incident demonstrates the mentality of some in the community and the importance of understanding the process. Still, I am positive that we will find a way to work within this context.

This will have a couple of side-effects and possibly some unintended consequences:

a) The bar for pre-publishing will become lower before the community accepts a paper. This means a higher volume of papers will appear and some personal way to sort through them will be necessary (already the volume of CS-related papers is overwhelming me... the "to-read" pile keeps growing.) This might mean more reliance to personal connections and trust, making the community more closed instead of bringing the openness desired.

b) The paper will actually take longer to be validated in a proper journal, although it will be cited in the meantime. In a fast moving community this might be an issue. This might give more power to the "difficult" conferences, such as NIPS, which are basically following the old review process. If you want your paper appearing faster, just submit to NIPS. Given the lack of true response/second review process in these conferences, I find these conferences to have more quirky and biased reviews than journals.

These are unintended consequences we will need to combat and take into account as we move to a system based on a pre-publication/open comments process. However, I still find the advantages worthy. A wide volume of comments and pre-publications suggestions will pressure an editor to reject a comment of an obnoxious reviewer (or one who has a personal grudge against you) instead of rejecting the paper.

Anyway... sorry for the long rant/comment :-) I hope it contributes something.

Image Credit: NASA/JPL/Space Science InstituteN00178189.jpg was taken on November 21, 2011 and received on Earth November 22, 2011. The camera was pointing toward SUTTUNGR, and the image was taken using the CL1 and CL2 filters. This image has not been validated or calibrated.

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

Single and multiple snapshot compressive beamforming

Single and multiple snapshot compressive beamforming by Peter Gerstoft, Angeliki Xenaki, Christoph F. Mecklenbräuker

For a sound field observed on a sensor array, compressive sensing (CS) reconstructs the direction-of-arrivals (DOAs) of multiple sources using a sparsity constraint. The DOA estimation is posed as an underdetermined problem expressing the acoustic pressure at each sensor as a phase-lagged superposition of source amplitudes at all hypothetical DOAs. Regularizing with an $\ell_1$-norm constraint renders the problem solvable with convex optimization, while promoting sparsity resulting in high-resolution DOA maps. Here, the sparse source distribution is derived using maximum a posteriori estimates for both single and multiple snapshots. CS does not require inversion of the data covariance matrix and thus works well even for a single snapshot resulting in higher resolution than conventional beamforming. For multiple snapshots, CS outperforms conventional high-resolution methods, even with coherent arrivals and at low signal-to-noise ratio. The superior resolution of CS is demonstrated with vertical array data from the SWellEx96 experiment for coherent multi-paths.

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

CS: The Secrecy of CS Measurements, Counting faces of randomly-projected polytopes, Compressive wireless arrays, Compressive beamforming and Mapping.

Here is a paper by Yaron Rachlin and Dror Baron on The Secrecy of Compressive Sensing Measurements that is evaluating whether it is possible to estimate the measurement matrix when one is given the final CS measurements. Dror and Yaron have also gone through the pain of explaining the paper in a more user-friendly summary than an abstract, I am grateful for that and I am copying verbatim their commentary (Thanks Dror and Yaron!).

Several recent papers mention the possibility that compressed sensing measurements are encrypted. In this paper, we investigate this claim. We consider a scenario where Alice has a secret message (in our model the message is a real, K-sparse signal) that she would like to share with Bob. She encodes this signal using an M by N Gaussian measurement matrix. Bob receives the measurements, and can recover the signal, because he also knows the measurement matrix (in practice, Alice and Bob could share the seed of a random number generator used to produce
the measurement matrix). Can an eavesdropper (Eve), who intercepts the measurements, recover the signal without knowing the measurement matrix? We evaluate this question using two well-established approaches to encryption: information-theoretic and computational.

First, we consider the stronger information-theoretic notion of perfect secrecy. This notion requires the mutual information between signals and measurements to be zero. However, the signals and measurements are statistically dependent, which rules out perfect secrecy. Second, we consider the weaker notion of computational secrecy, which means that Eve can only recover the signal with a prohibitively large computational cost. We prove that compressed sensing achieves a computational notion of secrecy in the face of an adversary attempting to use either ell_0 or ell_1 minimization. Our result hinges on a theorem that shows that with probability one Eve will recover an M-sparse explanation instead of a K-sparse explanation when using the wrong measurement matrix.

The abstract itself reads:

Results in compressed sensing describe the feasibility of reconstructing sparse signals using a small number of linear measurements. In addition to compressing the signal, do these measurements provide secrecy? This paper considers secrecy in the context of an adversary that does not know the measurement matrix used to encrypt the signal. We demonstrate that compressed sensing based encryption does not achieve Shannon’s definition of perfect secrecy, but can provide a computational guarantee of secrecy.

Here is a paper in which some of the findings were presented by Jared Tanner at Texas A&M: David Donoho and Jared Tanner in Counting faces of randomly-projected polytopes when the projection radically lowers dimension. The first part of the introduction reads:

1.1. Three surprises of high dimensions. This paper develops asymptotic methods

to count faces of random high-dimensional polytopes; a seemingly dry and unpromising pursuit. Yet our conclusions have surprising implications - in statistics,

probability, information theory, and signal processing - with potential impacts in

practical subjects like medical imaging and digital communications. Before involving

the reader in our lengthy analysis of high-dimensional face counting, we describe

three implications of our results.

• 1.1.1 Convex Hulls of Gaussian Point Clouds.
  
• 1.1.2. Signal Recovery from Random Projections.
  
• 1.1.3. How many gross errors can we efficiently correct?
  

Also found are three more papers from the Rice Compressed Sensing Resources:

Volkan Cevher, Ali Gurbuz, James McClellan, and Rama Chellappa, Compressive wireless arrays for bearing estimation of sparse sources in angle domain. The abstract reads:

Joint processing of sensor array outputs improves the performance of parameter estimation and hypothesis testing problems beyond the sum of the individual sensor processing results. When the sensors have high data sampling rates, arrays are tethered, creating a disadvantage for their deployment and also limiting their aperture size. In this paper, we develop the signal processing algorithms for randomly deployable wireless sensor arrays that are severely constrained in communication bandwidth. We focus on the acoustic bearing estimation problem and show that when the target bearings are modeled as a sparse vector in the angle space, functions of the low dimensional random projections of the microphone signals can be used to determine multiple source bearings as a solution of an ℓ1-norm minimization problem. Field data results are shown where only 10bits of information is passed from each microphone to estimate multiple target bearings.

Ali Gurbuz, James McClellan, and Volkan Cevher, A compressive beamforming method. The abstract reads:

Compressive Sensing (CS) is an emerging area which uses a relatively small number of non-traditional samples in the form of randomized projections to reconstruct sparse or compressible signals. This paper considers the direction-of-arrival (DOA) estimation problem with an array of sensors using CS. We show that by using random projections of the sensor data, along with a full waveform recording on one reference sensor, a sparse angle space scenario can be reconstructed, giving the number of sources and their DOA’s. The number of projections can be very small, proportional to the number sources. We provide simulations to demonstrate the performance and the advantages of our compressive beamformer algorithm.

Yasamin Mostofi and Pradeep Sen, Compressed mapping of communication signal strength. The abstract reads:

In this paper we consider a mobile cooperative network that is tasked with building a map of the received signal strength to a fixed station. By using the recent results in the area of compressed sensing, we show how the nodes can exploit the sparse representation of the channel’s spatial variations to build a map of the signal strength with minimal sensing. We furthermore propose a successive interference cancellation method for signal reconstruction based on a considerably incomplete set of measurements. The proposed method is an extension of the existing signal reconstruction strategies but with a considerably better performance. Finally, we present simulation results that show the performance of the proposed framework.

Credit: NASA/JPL/University of Arizona, Unconformity in Mars North Polar Layered Deposits (PSP_009390_2595) as taken by the HiRiSE camera

CS: calendar, CS Block Map-LMS Adaptive Filter, Democracy in Action, and more.

Thomas Strohmer sent me an e-mail mentioning the following:

Maybe you want to include in the calendar of events that a few compressed sensing sessions will take place in connection with the SPIE Wavelets conference, see this link: http://spie.org//app/program/index.cfm?fuseaction=conferencedetail&conference=7446&jsenabled=1

I'll add those shortly to the Compressive Sensing Calendar. Thank you Thomas !

Hadi Zayyani asked me to host his paper on my site, which is something I don't do often:

Compressed Sensing Block Map-LMS Adaptive Filter for Sparse Channel Estimation and a Bayesian Cramer-Rao Bound by Hadi Zayyani, Massoud Babaie-Zadeh and Christian Jutten. The abstract reads:

This paper suggests to use a Block MAP-LMS (BMAPLMS) adaptive filter instead of an Adaptive Filter called MAP-LMS for estimating the sparse channels. Moreover to faster convergence than MAP-LMS, this block-based adaptive filter enables us to use a compressed sensing version of it which exploits the sparsity of the channel outputs to reduce the sampling rate of the received signal and to alleviate the complexity of the BMAP-LMS. Our simulations show that our proposed algorithm has faster convergence and less final MSE than MAP-LMS, while it is more complex than MAP-LMS. Moreover, some lower bounds for sparse channel estimation is discussed. Specially, a Cramer-Rao bound and a Bayesian Cramer-Rao bound is also calculated.

In light of this hosting, here is a paper with a quite fitting title (from the Rice repository)

Democracy in Action: Quantization, Saturation, and Compressive Sensing by by Jason Laska, Petros Boufounos , Mark Davenport and Richard Baraniuk. The abstract reads:

Recent theoretical developments in the area of compressive sensing (CS) have the potential to significantly extend the capabilities of digital data acquisition systems such as analog-todigital converters and digital imagers in certain applications. The key hallmark of CS that has been the focus of the community so far is the fact that CS enables sub-Nyquist sampling for signals, images, and other data that have a sparse representation in some basis. In this paper, we explore and exploit another heretofore relatively unexplored hallmark, the fact that certain CS measurement systems are democratic, which means that each measurement carries roughly the same amount of information about the signal being acquired. Using the democracy property, we re-think how to quantize the compressive measurements in practical CS systems. If we were to apply the conventional wisdom gained from conventional Shannon-Nyquist uniform sampling, then we would scale down the analog signal amplitude (and therefore increase the quantization error) to avoid the gross saturation errors that occur when the signal amplitude exceeds the quantizer’s dynamic range. In stark contrast, we demonstrate a CS system achieves the best performance when we operate at a significantly nonzero saturation rate. We develop two methods to recover signals from saturated CS measurements. The first directly exploits the democracy property by simply discarding the saturated measurements. The second integrates saturated measurements as constraints into standard linear programming and greedy recovery techniques. Finally, we develop a simple automatic gain control system that uses the saturation rate to optimize the input gain.

Also found on the interwebs, some of these items are a little "old" but I don't think I cover them before:

A Fast Posterior Update for Sparse Underdetermined Linear Models by Lee Potter, Phil Schniter, and Justin Ziniel. The abstract reads:

A Bayesian approach is adopted for linear regression, and a fast algorithm is given for updating posterior probabilities. Emphasis is given to the underdetermined and sparse case, i.e., fewer observations than regression coefficients and the belief that only a few regression coefficients are non-zero. The fast update allows for a low-complexity method of reporting a set of models with high posterior probability and their exact posterior odds. As a byproduct, this Bayesian model averaged approach yields the minimum mean squared error estimate of unknown coefficients. Algorithm complexity is linear in the number of unknown coefficients, the number of observations and the number of nonzero coefficients. For the case in which hyperparameters are unknown, a maximum likelihood estimate is found by a generalized expectation maximization algorithm.

A Sparsity Detection Framework for On-Off Random Access Channels by Alyson Fletcher, Sundeep Rangan, Vivek Goyal. The abstract reads:

This paper considers a simple on–off random multiple access channel (MAC), where n users communicate simultaneously to a single receiver. Each user is assigned a single codeword which it transmits with some probability \lambda over m degrees of freedom. The receiver must detect which users transmitted. We show that detection for this random MAC is mathematically equivalent to a standard sparsity detection problem. Using new results in sparse estimation we are able to estimate the capacity of these channels and compare the achieved performance of various detection algorithms. The analysis provides insight into the roles of power control and multi-user detection.

Found on the Arxiv site:

Distributed MIMO radar using compressive sampling by Athina Petropulu, by Yao Yu, Athina Petropulu, H. Vincent Poor, H. Vincent Poor. The abstract:

A distributed MIMO radar is considered, in which the transmit and receive antennas belong to nodes of a small scale wireless network. The transmit waveforms could be uncorrelated, or correlated in order to achieve a desirable beampattern. The concept of compressive sampling is employed at the receive nodes in order to perform direction of arrival (DOA) estimation. According to the theory of compressive sampling, a signal that is sparse in some domain can be recovered based on far fewer samples than required by the Nyquist sampling theorem. The DOAs of targets form a sparse vector in the angle space, and therefore, compressive sampling can be applied for DOA estimation. The proposed approach achieves the superior resolution of MIMO radar with far fewer samples than other approaches. This is particularly useful in a distributed scenario, in which the results at each receive node need to be transmitted to a fusion center.

Presentations also found include:

• Andy Yagle, Non-Iterative Reconstruction of Sparse Images from Limited Data
• Phil Schniter, Lee Potter, and Subhojit Som, Sparse Reconstruction via Bayesian Variable Selection and Bayesian Model Averaging

Finally, Laurent Jacques mentions on his site that his recent paper entitled "Dequantizing Compressed Sensing with Non-Gaussian Constraints" co-written with D. K. Hammond and M. J. Fadili has been (slightly) updated.


Image Credit: NASA/JPL/Space Science Institute, image of Saturn taken on July 23 from Cassini.

Slides: Second Edition of the International Workshop on Compressed Sensing applied to Radar (CoSeRa 2013)

The second edition of the International Workshop on Compressed Sensing applied to Radar (CoSeRa 2013) took place September 17-19th 2013 in Bonn, Germany. Thank you to the organizers Joachim Ender, Fulvio Gini, and Holger Rauhut for putting up the slides online. From the program:

• Tuesday, 17. September 2013
• 9:15 - 10:00 Keynote: Yonina Eldar [Talk]
• Sub-Nyquist sampling and compressed processing with applications to radar
• Session A1: CS Theory and Signal Processing I
• Session Chair: Holger Rauhut
• 10:35 - 10:55 Boosting LASSO by Linear Embedding [Paper | Talk] Ashkan Panahi, Mats Viberg (Chalmers University, Sweden)
• 10:55 - 11:15 Dictionary Adaptation in Sparse Recovery Based on Different Types of Coherence [Paper | Talk] Henning Zörlein, Faisal Akram, Martin Bossert (Ulm University, Ulm, Germany)
• 11:15 - 11:35 Tensor-Based Dictionary Learning for Multidimensional Sparse Recovery: the K-HOSVD [Paper |Talk] Florian Römer, Giovanni Del Galdo (Ilmenau University of Technology, Ilmenau, Germany)
• 11:35 - 11:55 Two approaches to remote sensing via l1-minimization [Paper | Talk] Max Hügel (University of Bonn, Germany), Holger Rauhut (RWTH Aachen, Germany), Thomas Strohmer (University of California, USA)
• 11:55 - 12:15 An Analytical Study of Sparse Recovery Algorithms in Presence of an Off-Grid Source [Paper | Talk] Florian Römer, Roman Alieiev, Mohamed Ibrahim, Giovanni Del Galdo (Ilmenau University of Technology, Ilmenau, Germany)
• 12:15 - 13:40 Lunch Break (Lunch will be served in foyer)
• Session A2: CS Theory and Signal Processing II
• Session Chair: Yonina Eldar
• 13:40 - 14:00 Multiple Compressive Projection Measurement for Stepped Frequency Radar [Paper | Talk] Yun Lu, Dirk Plettemeier (Technische Universität Dresden, Germany)
• 14:00 - 14:20 A Group Sparsity Imaging Algorithm for Transient Radio Sources [Paper | Talk] Stephan Wenger (TU Braunschweig, Germany), Urvashi Rau (National Radio Astronomy Observatory, Socorro, USA), Marcus Magnor (TU Braunschweig, Germany)
• 14:20 - 14:40 Waveform Optimization for Compressive Sensing Radar Systems [Paper | Talk] Lyubomir Zegov (Delft University of Technology, Delft, The Netherlands), Radmila Pribić (Thales Nederland, Delft, The Netherlands), Geert Leus (Thales Nederland, Delft, The Netherlands)
• 14:40 - 15:00 Radar Implementation of Compressive Sensing: RICS Project Overview [Paper | Talk] G. Prisco, P. Vinetti, M. D’Urso (SELEX ES, Giugliano in Campania, Italy), F.Berizzi, T. Isernia, P. Rocca,Gilda Schirinzi (Consorzio Interuniversitario per le Telecomunicazioni, Parma, Italy), Ludger Prünte (Fraunhofer FHR, Wachtberg, Germany), I. Montiel Sanchez (European Defence Agency, Brussels, Belgiun)
• 15:00 - 15:20 How Sparse Sampling is Useful to Radar? [Paper | Talk] Stéphane Kemkemian, Myriam Nouvel (Thales Airborne Systems, France)
• 15:20 - 15:50 Coffee Break (Coffee will be served in foyer)
• Session A3: CS Radar I
• Session Chair: Fulvio Gini
• 15:50 - 16:10 On the Choice of Mixing Sequences for SNR Improvement in Modulated Wideband Convertor [Paper| Talk] Anastasia Lavrenko, Florian Römer, Reiner S. Thomä, Giovanni Del Galdo (Ilmenau University of Technology, Ilemnau, Germany)
• 16:10 - 16:30 Compressive Sampling Real-time Scalable Radar Signal Reconstruction Core [Paper | Talk] Michele Barbato, Gian Carlo Cardarilli, Marco Re, Ilir Shuli (Second university of Rome ”Tor Vergata”, Rome, Italy), Filippo De Stefani, Francesco Peluso, Valerio Tocca (SELEX Electronic Systems, Rome, Italy)
• 16:30 - 16:50 Some remarks on the Herman-Strohmer approach to high resolution CS-radar [Paper | Talk] Paweł Kasprzak, Leszek Lamentowski, Tadeusz Brenner (Bumar Elektronika, Warschau, Poland)
• 16:50 - 17:10 Bayesian Compressive Sensing in Radar Systems [Paper | Talk] Radmila Pribić (Thales Nederland, Delft, The Netherlands), Ioannis Kyriakides (University of Nicosia, Cyprus)
• 17:10 - 17:30 Sub-Nyquist Sampling for TDR Sensors: Finite Rate of Innovation with Dithering [Paper | Talk] Thomas Weber (SICK AG, 79183 Waldkirch, Germany), Bashar I. Ahmad (University of Cambridge, Cambridge CB2 1PZ, United Kingdom), Marc Ihle (University of Applied Sciences Karlsruhe, 76133 Karlsruhe, Germany)
• Wednesday, 18. September 2013
• Session A4: SAR
• Session Chair: Ali Cafer Gürbüz
• 8:30 - 8:50 SAR Image Compression via Independent Component Analysis and Compressive Sampling [Paper |Talk] Alessandra Budillon, Gilda Schirinzi (Università degli Studi di Napoli “Parthenope”, 80143 Napoli, Italy)
• 8:50 - 9:10 Initial Analysis of SNR / Sampling Rate Constraints in Compressive Sensing based Imaging Radar[Paper | Talk] Zhang Zhe, Zhao Yao, Jiang Chenglong, Zhang Bingchen, Hong Wen, Wu Yirong (Institute of Electronics, Chinese Academy of Sciences, Beijing, China)
• 9:10 - 9:30 Feature-Enhanced Imaging With Compressed/Fractional SAR Systems: Inverse Problem Formalism and l2-l1-Struictured Regularization Framework [Paper | Talk] Yuriy V. Shkvarko (Unidad Guadalajara, Mexico)
• 9:30 - 9:50 Compressed Sensing Application for Sparse Array Radar [Paper | Talk] Daojing Li, Ying Xi (Key Laboratory of Microwave Remoting Sensing, CAS, China)
• 9:50 - 10:10 Azimuth Ambiguity Suppression for SAR Imaging based on Group Sparse Reconstruction [Paper |Talk] Daojing Li, Liechen Li, Zhang Bingchen, Jiang Chenglong, Zhang Zhe (Institute of Electronics, Chinese Academy of Sciences. Beijing, China), Fang Jian (Xi’an Jiaotong University. Xi’an, China), Zhao Yao, Hong Wen, Wu Yirong (Institute of Electronics, Chinese Academy of Sciences. Beijing, China), Xu Zongben (Xi’an Jiaotong University. Xi’an, China)
• Session A5: ISAR + CS Radar II
• Session Chair: Ludger Prünte
• 10:40 - 11:00 Autofocus for CS Based ISAR Imaging in the presence of Gapped Data [Paper | Talk] Elisa Giusti, Sonia Tomei, Alessio Bacci, Marco Martorella, Fabrizio Berizzi (University of Pisa, Pisa, Italy)
• 11:00 - 11:20 ISAR Imaging of Space Objects via Compressed Sensing [Paper | Talk] Feng Wang, Ya-Qiu Jin (Fudan University, Shanghai 200433, China)
• 11:20 - 11:40 Sparse Delay-Doppler Image Reconstruction under Off-Grid Problem [Paper | Talk] Oguzhan Teke (Bilkent University, Ankara, Turkey), Ali Cafer Gürbüz (TOBB University of Economics and Technology, Ankara, Turkey) , Orhan Arikan (Bilkent University, Ankara, Turkey)
• 11:40 - 12:00 Optimized Sinus Wave generation with CS for Radar Application [Paper | Talk] Alexander Ens, A. Yousaf, T. Ostertag, L. M. Reindl (Universität Freiburg, Freibug, Germany)
• 13:30 - 14:15 Keynote: Marco Duarte [Talk]
• Parameter Estimation in Compressive Sensing: The Delay/Doppler Case
• Session A6: DOA + CS for optical systems
• Session Chair: Myrial Nouvel
• 14:15 - 14:35 On the Robustness of Bayesian Compressive Sensing for Directions-of-Arrival Estimation [Paper | Talk] Paolo Rocca, Giacomo Oliveri, Andrea Massa (University of Trento, Trento, Italy)
• 14:35 - 14:55 Imaging by Compressive Sensing: A 1-Pixel Camera & Beyond [Paper | Talk] Kevin F. Kelly (Rice University, Houston, USA)
• 14:55 - 15:15 Bayesian Compressive Sensing for Radar Systems and Applications - Recent Advances at the ELEDIA Research Center [Paper | Talk] Giacomo Oliveri, Paolo Rocca, Andrea Massa (University of Trento, Italy)
• 15:15 - 15:35 Bayesian compressive sensing based blind DOA estimation for multiple antennas [Paper | Talk] Fangqing Wen (Nanjing University of Aeronautics and Astronautics, China), Gong Zhang (Nanjing University of Aeronautics and Astronautics, China)
• Session A7: MTI and Interferometry
• Session Chair: Xiaoxing Zhu
• 16:05 - 16:25 Off-Grid Compressed Sensing for GMTI using SAR Images [Paper | Talk] Ludger Prünte (Fraunhofer FHR, Wachtberg, Germany)
• 16:25 - 16:45 Estimation of Moving Target Parameters using Compressive Sensing Methods [Paper | Talk] Manfred Hägelen (Fraunhofer FHR, Wachtberg, Germany)
• 16:45 - 17:05 Interferometric ISAR Imaging Based on Compressive Sensing [Paper | Talk] Wei Qiu (National University of Defense Technology, Changsha, China), Marco Martorella, Fabrizio Berizzi (University of Pisa, Pisa, Italy)
• 17:05 - 17:25 A comparative study in interferometric coherence optimization [Paper | Talk] Sofiane Tahraoui, Mounira Ouarzeddine, Boularbah Souissi (USTHB Algiers, Algeria)
• 17:25 - 17:45 Thermal dilation monitoring of single and double scatterers based on compressive sensing [Paper | Talk] Ma Peifeng, Lin Hui (Chinese University of Hong Kong, China)
• 17:45 - 18:05 Thomographic SAR Inversion by Generic Log-Barrier Algorithm - The Second Order Cone Programming Approach [Paper | Talk] Fillipo Biondi (University of l'Aquila, Italy)
• Thursday, 19. September 2013
• Foyer Hall 1
• Session A8: MIMO Radar
• Session Chair: Jacek Misiurewicz
• 9:00 - 9:20 A Compressive Sensing Approach to the Fusion of PCL sensors [Paper | Talk] Joachim Ender (Fraunhofer FHR, Wachtberg, Germany)
• 9:20 - 9:40 General MIMO Framework for Multipath Exploitation in Through-the-Wall Radar Imaging [Paper |Talk] Michael Leigsnering (Technische Universität Darmstadt, Darmstadt, Germany), Fauzia Ahmad, Moeness G. Amin (Villanova University, Villanova, PA, USA), Abdelhak M. Zoubir (Technische Universität Darmstadt, Darmstadt, Germany)
• 9:40 - 10:00 Off-Grid Compressive Sensing MIMO Radar [Paper | Talk] Michael Minner (Drexel University, Philadelphia, PA, USA)
• Session A9: CS in Acoustic and Sonar / Passive Radar and other Applications
• Session Chair: Gilda Schirinzi
• 10:30 - 10:50 Oceanographic Data Transmission: a Compressed Sensing-based Approach [Paper | Talk] Stefano Fortunati, Fulvio Gini, Maria S. Greco (University of Pisa, Italy), Raffaele Grasso (CMRE, Italy)
• 10:50 - 11:10 Compressive Re-Sampling for Speckle Reduction in Medical Ultrasound [Paper | Talk] Rick Mammone (Rutgers University, Piscataway, NJ 08854, USA), C. Podilchuk, L. Barinov, A. Jairaj, W. Hulbert, W. Stoddart (ClearView Diagnostics Piscataway, NJ 08854, USA)
• 11:10 - 11:30 Sonar imaging of structured sparse scene using template compressed sensing [Paper | Talk] Huichen Yan, Xudong Zhang, Shibao Peng (Tsinghua University, Beijing, China), Jia Xu (Beijing Institute of Technology, Beijing, China)
• 11:30 - 11:50 Compressed Sensing algorithms performance with superresolution in a passive radar [Paper | Talk] Jacek Misiurewicz, Janusz Kulpa (Warsaw University of Technology, Poland)
• 11:50 - 12:10 Retransmitted Jamming Method to LFM Radar Based on Compressed Sensing [Paper | Talk] Guochao Lao, Wei Ye (Academy of Equipment, Beijing, China), Hang Ruan (Academy of Equipment, Beijing, China)
• 13:30 - 14:15 Keynote: Justin Romberg [Talk]
• Subspace Matching from Compressed Samples with Applications to Radar
• Session A10: Detection and Classification
• Session Chair: Matthias Weiß
• 14:15 - 14:35 Extract Before Detect, N-Signal Complex Approximate Message Passing Applied to Radar Signals[Paper | Talk] Guy Desodt, Linda Aouchiche (Thales Air Systems, France), Olivier Rabaste (ONERA, France)
• 14:35 - 14:55 Correlation Matching Approach for Through-Wall Corner Detection [Paper | Talk] Eva Lagunas (Universitat Politecnica e de Catalunya (UPC), 08034 Barcelona, Spain), Moeness G. Amin (Villanova University, Villanova, PA 19085, USA), Fauzia Ahmad (Villanova University, Villanova, PA 19085, USA), Montse Nájar (Universitat Politecnica e de Catalunya (UPC), 08034 Barcelona, Spain)
• 14:55 - 15:15 Tracking of fluctuating target using stroboscopic sampling [Paper | Talk] Alex Bystrov, Marina Gashinova (University of Birmingham, United Kingdom)
• 15:15 - 15:35 Detection Performance from Compressed Measurements [Paper | Talk] Peter Tuuk, James H. McClellan (Georgia Institute of Technology, USA)

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

Matrix Factorization This Week.

Here is an interesting interaction, how can you give away your robust PCA to an open source project ?

Zeno Ganter reminded me an "older" paper  entitled: Bayesian Probabilistic Matrix Factorization using MCMC by Ruslan Salakhutdinov and Andriy Mnih. The interesting part is the attendant Matlab code,and its implementation by GraphLab. I will list both on the Matrix Factorization Jungle. In the meantime, Zeno also provided me with a list of additional information on matrix factorization:

Hi Igor 

.....

2. Matrix Completion for Implicit Feedback data

The "classical" MF methods for collaborative filtering/recommender systems optimize for RMSE, and can be used if there are explicit ratings by the users. In practice this is very often not the case, you only know about the users' past actions (Who bought what?). Then the completion problem becomes a bit more difficult, because it is a positive-only problem: You only have examples from one class and missing values.

There are several papers dealing with such kind of factorization problems, e.g.

(a) optimizing for pointwise errors:

Hu, Koren, Volinsky: Collaborative Filtering for Implicit Feedback Datasets. ICDM 2008

Pan, Zhou, Cao, Liu, Lukose, Scholz, Yang. 2008: One-Class Collaborative Filtering. ICDM 2008

(b) optimizing for ranking: Rendle, Freudenthaler, Gantner, Schmidt-Thieme: BPR: Bayesian

Personalized Ranking from Implicit Feedback

Speaking of ranking, there is also an approach that does matrix completion, but not optimized for RMSE, but NDCG on the known ratings:

Improving maximum margin matrix factorization Machine Learning Journal and European Conference on Machine Learning (ECML/PKDD 2008)

3. MF implementations in Open Source recommender system frameworks

• GraphLab (already listed)
• http://cofirank.org/ (single implementation of rating-based MF for ranking)
• Apache Mahout: http://mahout.apache.org/

There are implementations of MF for rating prediction and for implicit feedback data (at least there is a patch for it, not sure whether it is already in an official release). 

Our own package, MyMediaLite, also contains implementations of MF for rating prediciotn and for implicit feedback data. Additionally, we have a BPR-MF implementation. http://ismll.de/mymedialite

4. Parallel SGD for Matrix Completion

We also have an implementation of block-free SGD for RMSE matrix completion,

https://github.com/zenogantner/MyMediaLite/blob/master/src/MyMediaLiteExperimental/RatingPrediction/MultiCoreMatrixFactorization.cs

which uses the same idea as in Jellyfish and in Gemulla et al.'s KDD paper on distributed MF, which was published a bit earlier than Jellyfish:

R. Gemulla, E. Nijkamp, P. J. Haas, Y. Sismanis,  Large-Scale Matrix Factorization with Distributed Stochastic Gradient Descent. Both papers (the KDD paper and the Jellyfish one) come up with the same idea of independent updates, and both papers cover that simple and straighforward idea (nothing be ashamed of!) in a quite complex description. Nonetheless, both papers have plenty of additional ideas and interesting details thrown in, for example (Gemulla) using a bold-driver heuristic (from the neural network literature) for learning rate adaptation, and using subsamples to find good learning rates, or (Jellyfish) using some cores for also doing the example shuffling in parallel, thus avoiding bottlenecks.

......

Thanks Zeno. On arxiv, we had the following preprints:

Dynamic Matrix Factorization: A State Space Approach by John Z. Sun, Kush R. Varshney, Karthik Subbian. The abstract reads:

Matrix factorization from a small number of observed entries has recently garnered much attention as the key ingredient of successful recommendation systems. One unresolved problem in this area is how to adapt current methods to handle changing user preferences over time. Recent proposals to address this issue are heuristic in nature and do not fully exploit the time-dependent structure of the problem. As a principled and general temporal formulation, we propose a dynamical state space model of matrix factorization. Our proposal builds upon probabilistic matrix factorization, a Bayesian model with Gaussian priors. We utilize results in state tracking, such as the Kalman filter, to provide accurate recommendations in the presence of both process and measurement noise. We show how system parameters can be learned via expectation-maximization and provide comparisons to current published techniques.

An MDL framework for sparse coding and dictionary learning by Ignacio Ramírez, Guillermo Sapiro. The abstract reads:

The power of sparse signal modeling with learned over-complete dictionaries has been demonstrated in a variety of applications and fields, from signal processing to statistical inference and machine learning. However, the statistical properties of these models, such as under-fitting or over-fitting given sets of data, are still not well characterized in the literature. As a result, the success of sparse modeling depends on hand-tuning critical parameters for each data and application. This work aims at addressing this by providing a practical and objective characterization of sparse models by means of the Minimum Description Length (MDL) principle -- a well established information-theoretic approach to model selection in statistical inference. The resulting framework derives a family of efficient sparse coding and dictionary learning algorithms which, by virtue of the MDL principle, are completely parameter free. Furthermore, such framework allows to incorporate additional prior information to existing models, such as Markovian dependencies, or to define completely new problem formulations, including in the matrix analysis area, in a natural way. These virtues will be demonstrated with parameter-free algorithms for the classic image denoising and classification problems, and for low-rank matrix recovery in video applications.

Videos used for this paper can be found here.

This one is interesting for the folks interested in solving SDPs: Regularized Laplacian Estimation and Fast Eigenvector Approximation by Patrick O. Perry, Michael W. Mahoney. The abstract reads:

Recently, Mahoney and Orecchia demonstrated that popular diffusion-based procedures to compute a quick \emph{approximation} to the first nontrivial eigenvector of a data graph Laplacian \emph{exactly} solve certain regularized Semi-Definite Programs (SDPs). In this paper, we extend that result by providing a statistical interpretation of their approximation procedure. Our interpretation will be analogous to the manner in which $\ell_2$-regularized or $\ell_1$-regularized $\ell_2$-regression (often called Ridge regression and Lasso regression, respectively) can be interpreted in terms of a Gaussian prior or a Laplace prior, respectively, on the coefficient vector of the regression problem. Our framework will imply that the solutions to the Mahoney-Orecchia regularized SDP can be interpreted as regularized estimates of the pseudoinverse of the graph Laplacian. Conversely, it will imply that the solution to this regularized estimation problem can be computed very quickly by running, e.g., the fast diffusion-based PageRank procedure for computing an approximation to the first nontrivial eigenvector of the graph Laplacian. Empirical results are also provided to illustrate the manner in which approximate eigenvector computation \emph{implicitly} performs statistical regularization, relative to running the corresponding exact algorithm.

and finally, Fault Tolerant Matrix Pencil Method for Direction of Arrival Estimation by T. Yerriswamy, S.N. Jagadeesha. The abstract reads:

Continuing to estimate the Direction-of-arrival (DOA) of the signals impinging on the antenna array, even when a few elements of the underlying Uniform Linear Antenna Array (ULA) fail to work will be of practical interest in RADAR, SONAR and Wireless Radio Communication Systems. This paper proposes a new technique to estimate the DOAs when a few elements are malfunctioning. The technique combines Singular Value Thresholding (SVT) based Matrix Completion (MC) procedure with the Direct Data Domain (D^3) based Matrix Pencil (MP) Method. When the element failure is observed, first, the MC is performed to recover the missing data from failed elements, and then the MP method is used to estimate the DOAs. We also, propose a very simple technique to detect the location of elements failed, which is required to perform MC procedure. We provide simulation studies to demonstrate the performance and usefulness of the proposed technique. The results indicate a better performance, of the proposed DOA estimation scheme under different antenna failure scenarios.

Credit: NASA/JPL/University of Arizona


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