Tuesday, November 02, 2010

CS: Dimensionality reduction using compressed sensing and its application to a large-scale visual recognition task, Yves Meyer tribute, Recovering Lost Sensor Data through Compressed Sensing, Prior estimate-based compressed sensing in parallel MRI


In the CS world, we have :Dimensionality reduction using compressed sensing and its application to a large-scale visual recognition task by Son Lam Phung, Fok Hing Chi Tivive, Abdesselam Bouzerdoumz, Jie Yang. The abstract reads:
This paper presents a novel algorithm for the dimensionality reduction which employs compressed sensing (CS) to improve the generalization capability of a classifier, especially for large-scale data. Compared to traditional dimensionality reduction methods, the proposed algorithm makes no use of the problem-dependent parameters, nor does it require additional computation for the eigenvalue decomposition like PCA or LDA. Mathematically, the derived algorithm regards the input features as the dictionary in CS, and selects the features that minimize the residual output error iteratively, thus the resulting features have a direct correspondence to the performance requirements of the given problem. Furthermore, the proposed algorithm can be regarded as a sparse classifier, which selects discriminative features and classifies the training data simultaneously. Experimentally, the CS-based algorithm is tested with a hierarchical visual pattern recognition architecture. The simulation results show that not only does the proposed method utilize only 25% of full features while achieving the test accuracy of the original full architecture, but also its performance is competitive when compared to existing dimensionality reduction methods.

Also, Gabriel Peyre let me know of a series of presentations in honor of Yves Meyer at ENS Cachan. I just found a presentation by Zainul Charbiwala entitled Recovering Lost Sensor Data through Compressed Sensing and behind a paywall, we also have: Prior estimate-based compressed sensing in parallel MRI. by Wu B, Millane RP, Watts R, Bones PJ. The abstract reads:
Two improved compressed sensing (CS)-based image reconstruction methods for MRI are proposed: prior estimate-based compressed sensing (PECS) and sensitivity encoding-based compressed sensing (SENSECS). PECS allows prior knowledge of the underlying image to be intrinsically incorporated in the image recovery process, extending the use of data sorting as first proposed by Adluru and DiBella (Int J Biomed Imaging 2008: 341648). It does so by rearranging the elements in the underlying image based on the magnitude information gathered from a prior image estimate, so that the underlying image can be recovered in a new form that exhibits a higher level of sparsity. SENSECS is an application of PECS in parallel imaging. In SENSECS, image reconstruction is carried out in two stages: SENSE and PECS, with the SENSE reconstruction being used as a image prior estimate in the following PECS reconstruction. SENSECS bypasses the conflict of sampling pattern design in directly applying CS recovery in multicoil data sets and exploits the complementary characteristics of SENSE-type and CS-type reconstructions, hence achieving better image reconstructions than using SENSE or CS alone. The characteristics of PECS and SENSECS are investigated using experimental data.
.

Monday, November 01, 2010

CS: Graphical Models for CS, The Effect of Spatial Coupling on Compressive Sensing, Taken's Embedding, Super Greedy Algo, Chaotic Sensing Matrix for Compressive Sensing and abstracts of a past meeting

Today, we have a fresh arrival of new papers/preprints and the abstracts of a conference that took place in Germany back in October. The first paper shows us how 'fast' this new AMP solvers are (I'd like to get my hands on one of those), then, we have a paper that seems to cross the Donoho-Tanner phase transition . Then we have some results on Taken's embedding, a super greedy algorithm (that might taker a stab at overcomplete dictionaries) and finally some papers that use chaotic systems to produce measurement matrices that seem very suited for compressive sensing.

This paper surveys recent work in applying ideas from graphical models and message passing algorithms to solve large scale regularized regression problems. In particular, the focus is on compressed sensing reconstruction via ℓ1 penalized least-squares (known as LASSO or BPDN). We discuss how to derive fast approximate message passing algorithms to solve this problem. Surprisingly, the analysis of such algorithms allows to prove exact high-dimensional limit results for the LASSO risk.
This paper will appear as a chapter in a book on ‘Compressed Sensing’ edited by Yonina Eldar
and Gitta Kutynok.

Recently, it was observed that spatially-coupled LDPC code ensembles approach the Shannon capacity for a class of binary-input memoryless symmetric (BMS) channels. The fundamental reason for this was attributed to a "threshold saturation" phenomena derived by Kudekar, Richardson and Urbanke. In particular, it was shown that the belief propagation (BP) threshold of the spatially coupled codes is equal to the maximum a posteriori (MAP) decoding threshold of the underlying constituent codes. In this sense, the BP threshold is saturated to its maximum value. Moreover, it has been empirically observed that the same phenomena also occurs when transmitting over more general classes of BMS channels. In this paper, we show that the effect of spatial coupling is not restricted to the realm of channel coding. The effect of coupling also manifests itself in compressed sensing. Specifically, we show that spatially-coupled measurement matrices have an improved sparsity to sampling threshold for reconstruction algorithms based on verification decoding. For BP-based reconstruction algorithms, this phenomenon is also tested empirically via simulation. At the block lengths accessible via simulation, the effect is quite small and it seems that spatial coupling is not providing the gains one might expect. Based on the threshold analysis, however, we believe this warrants further study.
Takens' Embedding Theorem remarkably established that concatenating M previous outputs of a dynamical system into a vector (called a delay coordinate map) can be a one-to-one mapping of a low-dimensional attractor from the system state-space. However, Takens' theorem is fragile because even small imperfections can induce arbitrarily large errors in the attractor representation. We extend Takens' result to establish explicit, non-asymptotic sufficient conditions for a delay coordinate map to form a stable embedding in the restricted case of linear dynamical systems and observation functions. Our work is inspired by the field of Compressive Sensing (CS), where results guarantee that low-dimensional signal families can be robustly reconstructed if they are stably embedded by a measurement operator. However, in contrast to typical CS results, i) our sufficient conditions are independent of the size of the ambient state space (N), and ii) some system and measurement pairs have fundamental limits on the conditioning of the embedding (i.e., how close it is to an isometry), meaning that further measurements beyond some point add no further significant value. We use several simple simulations to explore the conditions of the main results, including the tightness of the bounds and the convergence speed of the stable embedding.

We study greedy-type algorithms such that at a greedy step we pick several dictionary elements contrary to a single dictionary element in standard greedy-type algorithms. We call such greedy algorithms {\it super greedy algorithms}. The idea of picking several elements at a greedy step of the algorithm is not new. Recently, we observed the following new phenomenon. For incoherent dictionaries these new type of algorithms (super greedy algorithms) provide the same (in the sense of order) upper bound for the error as their analogues from the standard greedy algorithms. The super greedy algorithms are computationally simpler than their analogues from the standard greedy algorithms. We continue to study this phenomenon.

Compressive Sensing (CS) is a new sampling theory which allows signals to be sampled at sub-Nyquist rate without loss of information. Fundamentally, its procedure can be modeled as a linear projection on one specific sensing matrix, which, in order to guarantee the information conservation, satisfies Restricted Isometry Property (RIP). Ordinarily, this matrix is constructed by the Gaussian random matrix or Bernoulli random matrix. In previous work, we have proved that the typical chaotic sequence - logistic map can be adopted to generate the sensing matrix for CS. In this paper, we show that Toeplitz-structured matrix constructed by chaotic sequence is sufficient to satisfy RIP with high probability. With the Toeplitz-structured Chaotic Sensing Matrix (TsCSM), we can easily build a filter with small number of taps. Meanwhile, we implement the TsCSM in compressive sensing of images.
Compressive sensing is a new methodology to capture signals at sub-Nyquist rate. To guarantee exact recovery from compressed measurements, one should choose specific matrix, which satisfies the Restricted Isometry Property (RIP), to implement the sensing procedure. In this letter, we propose to construct the sensing matrix with chaotic sequence following a trivial method and prove that with overwhelming probability, the RIP of this kind of matrix is guaranteed. Meanwhile, its experimental comparisons with Gaussian random matrix, Bernoulli random matrix and sparse matrix are carried out and show that the performances among these sensing matrix are almost equal.


# "Variational Inequalities and Morozov\'s Discrepancy Principle"
Anzengruber, Stephan
Variational Inequalities can be viewed as generalizations of classical source conditions and structural assumptions. In this talk we will show how, for non-linear ill-posed problems, Variational Inequalities can be combined with Morozov\'s Discrepancy principle to obtain convergence rates for Tikhonov Regularization with $\ell_p$ penalties, $p \geq 1$, which are well-known to promote sparsity.
# "Non-uniform sparse recovery with Gaussian matrices"
Ayaz, Ulas
Compressive sensing predicts that sufficiently sparse vectors can be recovered from highly incomplete information. Efficient recovery methods such as L1-minimization find the sparsest solution to certain systems of equations. Random matrices have become a popular choice for the measurement matrix. Indeed, near-optimal uniform recovery results have been shown for such matrices. In this note we focus on nonuniform recovery using Gaussian random matrices and `1-minimization. We provide a condition on the number of samples in terms of the sparsity and the signal length which guarantees that a fixed sparse signal can be recovered with a random draw of the matrix using L1- minimization. The constant 2 in the condition is optimal, and the proof is rather short compared to a similar result due to Donoho and Tanner. This is joint work with Holger Rauhut.
# "Regularization of linear integral equations with noisy data and noisy operator"
Bleyer, Ismael Rodrigo
Regularization methods for linear ill-posed problems $ Kf = g $ have been extensively investigated when there exists noisy measurements $g^{\delta}$ for the true data $g$. However, often also the operator is not known exactly. A common way to solve this problem is to use the regularized total least squares method. In our approach, we consider linear integral equations where we assume that both the kernel and the data are contaminated with noise, and use Tikhonov regularization for a stable reconstruction of both the kernel and the solution. Finally, we discuss computational aspects and develop an iterative shrinkage-thresholding algorithm for the reconstruction, and provide first numerical results.
# "Multilevel Preconditioning and Adaptive Sparse Solution of Inverse Problems"
Dahlke, Stephan
Multilevel Preconditioning and Adaptive Sparse Solution of Inverse Problems We are concerned with the efficient numerical solutaion of minimization problems in Hilbert spaces involving sparsity constraints. These optimization problems arise, e.g., in the context of inverse problems. We analyze a very efficient variant of the well-known iterative soft shrinkage algorithm for large or even infinite dimesnional problems. This algorithm is modified in the following way. Instead of prescribing a fixed threshold parameter, we use a decreasing thresholding strategy. Moreover, we use suitable adaptive schemes for the approximation of the infinite matrix-vector products. We also derive a block multiscale preconditioning technique which allows for local well-conditioning of the underlying matrices and for extending the concept of restricted isometry property to infinitely labelled matrices. The careful combination of these ingredients gives rise to numerical schemes that are guaranteed to cnverge with esponential rate, and which allow for the controlled inflation of the support size of the iterations. We also present numerical experiments that confirm the applicability of our approach. (Joint work with M. Fornasier and T. Raasch)
# "Linear Convergence Rates of l1-Regularization"
Haltmeier, Markus
In this talk we study the stable solution of ill-posed equations
Ax = y
where A : X → Y is a linear operator between Hilbert spaces X and Y . If this equation is ill-posed, then the solution does not depend continuously on the data y. In order to stably solve the equation, stabilization methods have to be applied. The most widely used stabilization technique is Tikhonov regularization
Τy(x) := ||Ax-y||2 + αR(x) → min.
Here R is a penalty functional and α \gt 0 is the regularization parameter.
In the recent years - motivated by the success of compresses sensing - the use of l1 penalty
R(x) = ||x||l1 := ∑λ ∈ Λ|φλ,x|
became very popular.(Here (φλ)λ ∈ Λ is some basis of X.) In this talk we study Tikhonov regularization with l1 penalty term. In particular, we show that the range condition (ran(A*) ∩ R(x+) ≠ ∅) together with a certain injectivity condition allows linear error estimates (convergence rates) between the solution x+ and minimizers of Τα,y. Moreover, we show that the range condition is even necessary for this linear convergence rate. This is talk is based on joint work with M. Grasmair and O. Scherzer.

* M. Grasmair, M. Haltmeier, and O. Scherzer. Necessary and sufficient conditions for linear convergence of l1-regularization. Reports of FSP S105 - \"Photoacoustic Imaging\" 18, University of Innsbruck, Austria, 2009.


# "Compressed Sensing in Infinite Dimensions"
Hansen, Anders C.
Compressed sensing is a great tool for solving inverse problems and it has a wide range of applications in signal processing and medical imaging. However, the current theory covers only problems in finite dimensions, and thus there are plenty of infinite dimensional inverse problems that are not covered by the existing results. In this talk I will show how the finite dimensional theory can be extended to include problems in infinite dimensions. This allows for recovery of much more general objects such as analog signals and infinite resolution images. The tools required come from probability, operator theory, optimization and geometry of Banach spaces. I\'ll give an introduction to what is already known (accompanied by numerical examples) and discuss some of the open questions.
# "Compressed sensing for ill-posed problems: recovery principles and accuracy estimates"
Herrholz, Evelyn
This talk is concerned with compressive sampling strategies and sparse recovery principles for linear and ill-posed problems. We provide compressed measurement models and accuracy estimates for sparse approximations of the solution of the underlying inverse problem. Thereby, we rely on Tikhonov variational and constraint optimization formulations. One essential difference to the classical compressed sensing framework is the incorporation of a joint sparsity measure allowing the treatment of infinite dimensional reconstruction spaces. The theoretical results are furnished with a numerical experiment.
# "New and improved Johnson-Lindenstrauss embeddings via the Restricted Isometry Property"
Krahmer, Felix
The Johnson-Lindenstrauss (JL) Lemma states that any set of p points in high dimensional Euclidean space can be embedded into O(δ ^{-2} log(p)) dimensions, without distorting the distance between any two points by more than a factor between 1 - δ and 1 + δ . We establish a new connection between the JL Lemma and the Restricted Isometry Property (RIP), a well-known concept in the theory of sparse recovery often used for showing the success of l_1-minimization. Consider an m x N matrix satisfying the (k, δ _k)-RIP with randomized column signs and an arbitrary set E of O(e^k) points in R^N. We show that with high probability, such a matrix with randomized column signs maps E into R^m without distorting the distance between any two points by more than a factor of 1 +/- 4 δ _k. Consequently, matrices satisfying the Restricted Isometry of optimal order provide optimal Johnson-Lindenstrauss embeddings up to a logarithmic factor in N. Moreover, our results yield the best known bounds on the necessary embedding dimension m for a wide class of structured random matrices. In particular, for partial Fourier and partial Hadamard matrices, our method optimizes the dependence of m on the distortion δ : We improve the recent bound m = O(δ ^{-4} log(p) log^4(N)) of Ailon and Liberty (2010) to m = O(δ ^{-2} log(p) log^4(N)), which is optimal up to the logarithmic factors in N. Our results also yield new Johnson-Lindenstrauss bounds for several deterministic matrices with randomized column signs. This is joint work with Rachel Ward.
# "Efficient Calculation of Sparse Solutions for Inverse Problems"
Lakhal, Aref
We present an efficient method to regularize ill-posed problems with sparsity as prior knowledge. We combine mollification methods with standard techniques of optimization to derive an efficient algorithm for solving inverse problems with L1- constrains. Numerical tests illustrate the robustness of the algorithm.
# "Exact recovery for linear ill-posed problems with l^1 regularization"
Lorenz, Dirk
Ill-posed problems are problems in which the solution does not depend continuously on the data. In this talk we consider Tikhonov regularization of such problems, and especially focus on sparse regularization. By combining techniques from ill-posed problems and sparse recovery we show, that it it is possible to reconstruct the exact support of the unknown solution even for ill-posed problems. We illustrate our results on the ill-posed problem of digital particle holography.
# "Generalization of the Neural Gas for Learning Sparse Codes"
Martinetz, Thomas
The Neural Gas is a very simple but efficient algorithm for vector quantization which has found widespread applications. We show how it can be extended to learning linear subspaces and be cast into the framework of sparse coding. It compares favorably to other approaches like k-SVD and MOD.
# "Exact Sparse Solutions of Underdetermined Linear Equations"
Pfetsch, Marc
In this talk I will review combinatorial optimization techniques to find a sparsest solution of underdetermined linear equations. The corresponding exact methods are based on branch-and-cut. Not surprisingly, these techniques are computationally much more involved than heuristics such as basis pursuit. The solutions of this and other heuristics will be compared to the exact values. I will try to show the limits and possibilities of the currently available exact approaches.
# "Compressive Sensing and Function Recovery in High Dimensions"
Rauhut, Holger
The talk reviews some basics on compressive sensing, in particular, on recovery of functions that are sparse in bounded orthonormal systems (e.g. the trigonometric system) from randomly chosen samples. We apply then compressive sensing techniques for the recovery of functions in high dimensions.
# "Iterative sparse recovery and regularization theory"
Teschke, Gerd
We shall be concerned with sparse recovery algorithms for inverse and ill-posed problems. In particular, we consider a projected steepest descent method, its stabilization and corresponding regularization results.
# "An Infeasible-Point Subgradient Method and Computational Comparison for l¹-Minimization"
Tillmann, Andreas
The l¹-minimization problem min{ ||x||_1 : Ax=b } , also known as Basis Pursuit (BP), has become important in Compressed Sensing due to its ability to sometimes yield the sparsest solution of the underdetermined system Ax=b. In the past few years, a lot of new algorithms solving (BP) or some (possibly regularized) variant of it have been developed. We introduce a subgradient scheme which -- unlike typical projected subgradient methods -- is not required to maintain feasibility of the iterates throughout the algorithmic progress. Convergence of this method (ISML1) to an optimal feasible point for (BP) can be proven under certain reasonable assumptions. In the second part of the talk we will present results of a computational comparison of various state-of-the-art l¹-solvers and our method. We also show how a new optimality check can speed up these solvers and at the same time dramatically improve the solution quality. (Joint work with D. Lorenz and M. Pfetsch)
# "Quality assessment of the l1 penalization method for sparse recovery"
Verhoeven, Caroline
The l1 penalization method is often used for sparse recovery in (linear) inverse problems. Most research on the effectiveness of this method focuses on measurement matrices with mutual incoherent columns or which satisfy the restricted isometry property. We will study matrices which do not satisfy these properties. Some typical recovery errors are computed in order to show how they are influenced by the sparsity of the desired solution, the noise level in the data, the number of data and the singular value spectrum of the matrix. These results are compared to known theoretical bounds. We also illustrate the ability of this method to predict relative errors on a magnetic tomography example. (joint work with I. Loris)
# "Regularization results for inverse problems with sparsity functional"
Wachsmuth, Gerd
We consider an optimization problem of the type \begin{equation} \left\{ \begin{aligned} \text{Minimize}\quad & F(u) = \frac12 \| \mathcal{S} u - z_\delta \|_{H}^2 + \alpha \, \| u \|_{L^2(\Omega)}^2 + \beta \, \| u \|_{L^1(\Omega)} \\ \text{such that}\quad & u \in U_\textup{ad} \subset L^2(\Omega). \end{aligned} \right.\tag{$\textbf{P}_{\alpha,\delta}$} \label{eq:P} \end{equation} Here, $\Omega \subset \mathbb{R}^n$ is a bounded domain, $H$ is some Hilbert space, $\mathcal{S} \in \mathcal{L}(L^2(\Omega), H)$ compact (e.g.\ the solution operator of an elliptic partial differential equation), $\alpha \gt 0$, and $\delta, \beta \ge 0$. The problem~\eqref{eq:P} can be interpreted as an inverse problem as well as an optimal control problem. Let us denote the solution with $u_{\alpha,\delta}$. The estimate $\| u_{\alpha,0} - u_{\alpha,\delta}\|_{L^2(\Omega)} \le \delta \, \alpha^{-1/2}$ for the error due to the noise level $\delta$ is well known for $\beta = 0$ and the proof can be extended to the case $\beta \gt 0$. A typical way to estimate the regularization error as $\alpha \searrow 0$ is via a source condition, e.g.\ $u_{0,0} = \mathcal{S}^\star w$ with some $w \in H$. This yields $\| u_{\alpha,0} - u_{0,0} \|_{L^2(\Omega)} \le C \, \alpha^{1/2}$. But if pointwise constraints are present ($U_\textup{ad} = \{ u \in L^2(\Omega) : u_a \le u \le u_b \}$), $u_{0,0}$ often is bang-bang, i.e.\ $u_{0,0}(x) \in \{u_a, 0, u_b\}$ a.e.\ in $\Omega$. Hence, $u_{0,0} \\notin H^1(\Omega)$ and by $\operatorname{range}(\mathcal{S}^\star) \subset H^1(\Omega)$ a source condition with $\mathcal{S^\star}$ can not hold. In this talk we present a new technique for deriving rates of the regularization error using a combination of a source condition and a regularity assumption on the adjoint variable $p_{0,0} = \mathcal{S}^\star(z_0 - \mathcal{S} u_{0,0})$. If the measure of $\big\{ \big| |p_{0,0}| - \beta \big| \le \varepsilon \big\} \le C \, \varepsilon$ for all $\varepsilon \ge 0$ it is possible to show $\| u_{\alpha,0} - u_{0,0} \|_{L^2(\Omega)} \le C \, \alpha^{1/2}$ without a source condition. We present examples showing that the error rates are sharp.
# "Generalized Tikhonov regularization with Bregman discrepany"
Worliczek, Nadja
This talk will deal with generalized Tikhonov regularization with Bregman distances as discrepany term. We give a short motivation for using them by means of statistical inversion theory where maximum a posteriori estimators of the solution of inverse problems are often gained by minimizing such functionals. Furthermore we will examine some basic properties of these sort of Tikhonov functionals.
# "Truncated Soft Shrinkage Iteration with Discrepancy Based Stopping Rule"
Zhariy, Mariya

Sunday, October 31, 2010

Of M&M's, Gravitational Lenses, the Hubble and the Last Space Shuttle Mission.

In The Accidental Astrophysicists, Dick Lipton reminded us how a result found in math put an end to a conjecture devised in astrophysics. It is a very compelling story that involves non other than a serendipitous Math department's copier. The result bears on gravitational lenses which happened to be discovered using the WFPC2 Camera on-board the Hubble telescope (before WFPC2 was installed, we had many blurred images of the sky). It so happens that this camera was installed by the crew of the Servicing Mission 1 on STS-61 in 1993 which included Tom Akers and Katy Thornton. Both were flying with us on the KC-135 a few months before that flight, and I believe we shared M&Ms on that flight..

During breaks, we would throw M&Ms at each other for fun. In restrospect,  I can only imagine if one of those M&Ms had flown right into the eye ball of one of these two; the mission would have been delayed and then....we never know. So yes, I feel connected to gravitational lenses in a unique way that involves M&Ms. More seriously, in two days, barring any additional funding, the space Shuttle will fly for the last time. The last servicing mission for the Hubble took place a year ago. The Hubble will never be re-serviced again and will eventually crash in the ocean.
Credit: NASA, HST, ESA

Friday, October 29, 2010

CS: CS-ECG, ParallelCamp, Une Competition, UPS Delivers Optimal Phase Diagram in High Dimensional Variable Selection, Diffuse Optical Tomography, Exploiting Statistical Dependencies

I was at another meeting last week, the Parallel Camp  a specific instance of a Barcamp, a networking event of sorts on a specific subject. Here the meeting was about parallelism and mostly GPUs. To get some conversation going, I made this presentation entitled: Parallel Computing for Compressive Sensing: What is it Good For ?. The public was pretty sparse but focused as I was competing with a much larger session. One of the fascinating things was that I kept on talking about sensors and how CS could be affecting them and how,  I  believe, parallel  computing fitted right into this new paradigm. Yet some of the people in the audience eventually asked about what a sensor was. My take from this is that sensors are always taken for granted: i.e. nobody wants to be Superman and have X-ray vision  anymore:-) because everybody is convinced that people working for CSI can do anything. On the other hand, the power level of GPUs sure makes the issue of reducing power at the sensor level a little quaint issue. Of note, Eric Mahé of MassiveRand, one of the organizers of the meeting, pitched a GPU based solution that spits out random numbers that can never be reproduced. Other discussions included some of the folks involved in Finance and the need to get good Random Numbers out of current technology (an issue Christian Robert just talked about recently on his blog). Most of the answers on the subject were pretty much summarized in the comment of that blog entry. Also I did not realize this but a GPU can currently spit out 6 Gbit of random numbers per second for a memory on the card reaching 6 GB. The PCI Express link between the CPU and the GPU seems to really be the main bottleneck as far as I could tell. The viewpoint of Compressive Sensing tells me that in order to use GPUs at their full extent, maybe we ought to be looking at how the 6Gb/s of RNG can be used on the GPU or on peripherals like the CRT/LCDs that have direct access to this flood of data. On a different note, you may notice in the presentation one of my new subject of interest...

Emily Allstot sent me the following:
Hello,

I am an undergraduate Electrical Engineering student at the University of Washington, doing research related involving compressed sensing. I also have been a fan of your blog for a while.

For once, I actually have some interesting things to share!

Our department has invited Emmanuel Candes to give a colloquium on December 7, 2010, and anyone in the Seattle area who is interested can come. Videos will also be posted afterward, at the link.

Also, next week is the BioCAS 2010 conference in Paphos, Cyprus. I will be presenting my very first publication during the BioSignal Processing lecture session. The paper is titled, "Compressive Sampling of ECG Bio-Signals: Quantization Noise and Sparsity Considerations" by Emily Allstot, Andrew Y. Chen, Anna M.R. Dixon, Daibashish Gangopadhyay, and David J. Allstot (Dept. of Electrical Engineering, Univ. of Washington). This paper is part of the groundwork for integrated circuit implementations of CS that are being designed by the PhD students in our group.

This is the abstract:

"Compressed sensing (CS) is an emerging signal processing paradigm that enables the sub-Nyquist processing of sparse signals; i.e., signals with significant redundancy. Electrocardiogram (ECG) signals show significant time-domain sparsity that can be exploited using CS techniques to reduce energy consumption in an adaptive data acquisition scheme. A measurement matrix of random values is central to CS computation. Signal-to-quantization noise ratio (SQNR) results with ECG signals show that 5- and 6-bit Gaussian random coefficients are sufficient for compression factors up to 6X and from 8X-16X, respectively, whereas 6-bit uniform random coefficients are needed for 2X-16X compression ratios. "
....
Thanks Emily. I look forward to see how some of these encodings (quantized Gaussian random) perform compared to the expander graph approach of the EPFL folks.


In a different direction,  Matthijs den Besten is organizing a new "Compressive Sesnsing" competition not unlike that the one Matlab ran a while back. It's in French. and called "Le grand concours de programmation MATLAB". There are prizes associated with winning the big prize or any of the intermediary prizes. Bonne Chance!

Here is a new paper investigating the Donoho-Tanner phase transition from a statistics viewpoint with a new algorithm: UPS Delivers Optimal Phase Diagram in High Dimensional Variable Selection by Pengsheng Ji, Jiashun Jin. The abstract reads:
Consider linear regression in the so-called regime of p much larger than n. We propose the UPS as a new variable selection method. This is a Screen and Clean procedure [Wasserman and Roeder (2009)], in which we screen with the Univariate thresholding, and clean with the Penalized MLE. In many situations, the UPS possesses two important properties: Sure Screening and Separable After Screening (SAS). These properties enable us to reduce the original regression problem to many small-size regression problems that can be fitted separately. We measure the performance of variable selection procedure by the Hamming distance. In many situations, we find that the UPS achieves the optimal rate of convergence, and also yields an optimal partition of the so-called phase diagram. In the two-dimensional phase space calibrated by the signal sparsity and signal strength, there is a three-phase diagram shared by many choices of design matrices. In the first phase, it is possible to recover all signals. In the second phase, exact recovery is impossible, but it is possible to recover most of the signals. In the third phase, successful variable selection is impossible. The UPS is able to recover most of the signals as long as successful variable selection is possible. The lasso and the subset selection are well-known approaches to variable selection. However, somewhat surprisingly, there are regions in the phase space where neither of them is rate optimal, even in very simple cases. The lasso is non-optimal for it is too loose on false positives, and the subset selection is non-optimal for it is too harsh on true positive clusters.
The figures are using a different set of variables than the ones we are accustomed to in Donoho-Tanner phase transition, but I found the following Rosetta stone description enlightening (yes statisticians speak Greek to me, not that there is anything wrong with speaking Greek!). From the text:
....The lasso and the subset selection (also known as the L1- and L0-penalization methods, respectively) are well-known approaches to variable selection. However, somewhat surprisingly, there are regions in the phase space where neither the lasso nor the subset selection is rate optimal, even for very simple. The lasso is non-optimal because it is too loose in filtering out fake signals (i.e. noise that is highly correlated with a signal), and the subset selection is non-optimal because it tends to kill one or more signals when signals appear in pairs, triplets, etc..
Similarly, Sergey points me to this arxiv preprint which made a passing reference to CS: Theory and Applications of Robust Optimization by Dimitris Bertsimas, David B. Brown, Constantine Caramanis. The abstract reads:
In this paper we survey the primary research, both theoretical and applied, in the area of Robust Optimization (RO). Our focus is on the computational attractiveness of RO approaches, as well as the modeling power and broad applicability of the methodology. In addition to surveying prominent theoretical results of RO, we also present some recent results linking RO to adaptable models for multi-stage decision-making problems. Finally, we highlight applications of RO across a wide spectrum of domains, including finance, statistics, learning, and various areas of engineering.
Reading the paper yields to this other paper I had mentioned back in April:
which makes a statement about Robust Linear Regression which in our world translates into multiplicative noise. More Rosetta Stone moments....In the meatime, you might also be interested in the NIPS 2010 Workshop, entitled Robust Statistical learning (robustml):

Checking the Google and Arixv, I finally got the following two papers:

Diffuse optical tomography (DOT) allows tomographic (3D), non-invasive reconstructions of tissue optical properties for biomedical applications. Severe under-sampling is a common problem in DOT which leads to image artifacts. A large number of measurements is needed in order to minimize these artifacts. In this work, we introduce a compressed sensing (CS) framework for DOT which enables improved reconstructions with under-sampled data. The CS framework uses a sparsifying basis, ℓ1-regularization and random sampling to reduce the number of measurements that are needed to achieve a certain accuracy. We demonstrate the utility of the CS framework using numerical simulations. The CS results show improved DOT results in comparison to “traditional” linear reconstruction methods based on singular-value decomposition (SVD) with ℓ2-regularization and with regular and random sampling. Furthermore, CS is shown to be more robust against the reduction of measurements in comparison to the other methods. Potential benefits and shortcomings of the CS approach in the context of DOT are discussed.

Signal modeling lies at the core of numerous signal and image processing applications. A recent approach that has drawn considerable attention is sparse representation modeling, in which the signal is assumed to be generated as a combination of a few atoms from a given dictionary. In this work we consider a Bayesian setting and go beyond the classic assumption of independence between the atoms. The main goal of this paper is to introduce a statistical model that takes such dependencies into account and show how this model can be used for sparse signal recovery. We follow the suggestion of two recent works and assume that the sparsity pattern is modeled by a Boltzmann machine, a commonly used graphical model. We show that for general dependency models, exact MAP estimation of the sparse representation becomes computationally complex. To simplify the computations, we propose a greedy approximation for the MAP estimator. We then consider a special case where exact MAP is feasible, by assuming that the dictionary is unitary and the dependency model corresponds to a certain sparse graph. Exploiting this structure, we develop an efficient message-passing algorithm that recovers the underlying signal. The effectiveness of our developed pursuit methods is demonstrated on synthetic signals, where we compare the denoising performance to that of previous recovery methods that do not exploit the statistical dependencies. Finally, when the model parameters defining the underlying graph are unknown, we suggest an algorithm that learns these parameters directly from the data, leading to an iterative scheme for adaptive sparse signal recovery.

Thursday, October 28, 2010

CS: A video, some stats, An old CS system ? Very High Resolution SAR Tomography via Compressive Sensing, Around the blogs in 80 hours,a PhD position and more.

While using the Google, I was just reminded of the following video of Emmanuel Candes' presentation in EE380 at Stanford. I like the first slide.

Blogger, the blogging platform of this site, now provides public stats on pageviews. Since July 1 st, 2010, we've had more than 100,000 pageviews. It looks staggering at first sight....

...and it is still staggering at second sight :-). If you come to the site, you'll also notice the posts that have been most popular in the past seven days.


Add to that, more than 50,000 views of entries as read through the Feedreaders. I may expand on that later but the type of subjects and entries most viewed on the blog and through the feed are markedly different.


Mahesh Shastry, one of the author of one of the first paper using the Donoho-Tanner transition for checking on a potential hardware set-up, just sent me the following:
I am a grad student at Penn State. This email concerns an historic fact that has possible connections to compressive sensing, that I was recently made aware of. My thesis adviser (Ram M. Narayanan) pointed me to a patent (by Alfred A. Wolf) from 1974 which proposes using a type of random projections for speech signal processing. Please find attached. It makes interesting read!
It is here: A speech compression system.by Alfred A. Wolf. The encoding scheme is shown here:



Whereas the reconstruction schematics can be found in patent 3,746,791 by the same author in Speech Synthesizer Utilizing White Noise


Indeed it looks similar, at the very least it looks similar to the 'crazy' random filters in  Random Filters For Compressive Sampling And Reconstruction. However, here are several differences:
  • the scheme described in the patent does not assume sparsity of the signal (maybe the signal is sparse by default for it to work, so this is not an exclusion property).
  • the complexity of the reconstruction does not seem high (which doesn't preclude it from being part of the club), but more importantly
  • the random noise that is encoding the signal does not seem to be stored for use in the decoding stage..
And that, my friend, is a killer... I think. Because of this last  feature of the system I would not call  this system an instance of compressive sensing, and you ? You can answer the poll below.














Thanks Mahesh .

While doing a search I found the following presentation by Zhu Xiaoxiang on Very High Resolution SAR Tomography via Compressive Sensing.

In the past weeks, here are some of the blog entries that got my interest:
Laurent Jacques sent me the following:

Opening of a PhD position:

"Optical Inverse Problem Solving in 3-D Deflectometry"

<http://www.tele.ucl.ac.be/~jacques/index.php/Main/PHD25102010>

(starting date: January 1st, 2011, application deadline: November 19th, 2010. )

Advisors:

   * Dr Laurent Jacques (ICTEAM/ELEN, UCL)
   * Prof. Philippe Antoine (IMCN/NAPS, UCL)
   * Prof. Benoît Macq (ICTEAM/ELEN, UCL)

Optical Framework:

Improved functional performance is a general trend in ocular surgery today. As an example, multifocal intraocular lens (IOL) achieves different optical powers, as such to enable good near and distant vision. There are two types of multifocal lenses. A refractive multifocal lens is made of concentric rings whose refractive powers alternate from centre to periphery. Diffractive multifocal lens uses light diffraction at an interference grid made of micrometric steps. Such complex surfaces are a real challenge both for manufacturing and for characterization.

This position opening takes place in a 3-year regional project (DETROIT), funded by the Belgian Walloon Region. This project aims at characterizing surfaces by optical deflectometry. The principle is to measure the deviation of the light reflected by each point of the surface. This technique is an interesting alternative to interferometry in order to estimate the surface topography. Indeed measuring the deviation angle instead of the height has several advantages. It is insensitive to vibrations as it is not based on interferences. It is more effective in detecting local details and object contours than height measurement. In deflectometry, the shape of an object is numerically reconstructed from the gradient data with a high accuracy. As an example, 10nm flatness deviation over a 50mm window glass can be observed with high accuracy instrument.

Experimentally, the very short radius of curvature of the IOLs requires the use of wide acceptance optics as such to collect light that is reflected in a large range of angles. The drawback is the very narrow field of view. In order to reduce the acquisition time, a device that images the whole lens shall be preferred but inevitable distortion of the image will be numerically corrected based on the knowledge of instrument response. This solution is challenging but very attractive for industrial perspectives.

Numerical Methods:

Nowadays, assuming that a signal (e.g., a 1-D signal, an image or a volume of data) has a sparse representation, namely that this signal is linearly described with few elements taken in a suitable basis, is an ubiquitous hypothesis validated in many different scientific domains. Interestingly, this sparsity assumption is the heart of methods solving inverse problems, namely those estimating a signal from some linear distorting observations. Sparsity stabilizes (or regularizes) these signal estimation techniques often based on L1-norm (or Total Variation norm) minimization and greedy methods.

This PhD position concerns the application of the sparsity principle for modeling and solving the optical inverse problem described in the previous section, that is, the reconstruction of the undistorted image of the IOL from the experimental measurements. This research will be carried out in collaboration with a postdoctoral researcher hired for one year on the same project.

Job description:

The student will develop mathematical methods and algorithms for reconstructing the undistorted IOL image from the experimental measurements, taking into account (and modeling) the particularities of the sensing systems. Calibration of the response of the instrument will be carried out by another partner of the project. However, a close collaboration between the two teams is necessary. Moreover, the PhD student will be co-supervised by a postdoctoral researcher hired on the same topic and funded by the same project.

The optical development takes place in the 3-year project DETROIT. It involves two industrial partners, Physiol and Lambda-X and 3 university partners. Physiol is well-known for its development of IOL. Lambda-X has a large experience in optical characterization of optical components by means of deflectometry. The leading academic partner is the Atomic, Molecular and Optical Physics Laboratory (IMCN/NAPS) of University of Louvain (UCL, Louvain-la-Neuve, Belgium), helped by two other Belgian university partners: the Active Structures Laboratory of the University of Brussels (ASL, ULB), in charge of the development of fast adaptive optics, and the Communications and Remote Sensing laboratory TELE (ICTEAM/ELEN, UCL) which is responsible of the IOL image reconstruction and post-processing algorithms.

Research activity will be carried out in the TELE Laboratory, and partly at PAMO and at Lambda-X offices in Nivelles, Belgium.


Candidate's Profile:

* M.Sc. in Applied Mathematics, Physics, Electrical Engineering, or Computer Science;
* Knowledge (even partial) in the following topics constitutes assets:
 o Convex Optimization methods,
 o Signal/Image Processing,
 o Classical Optics,
 o Compressed Sensing and inverse problems.
* Experience with Matlab, C and/or C++.
* Good communications skills, both written and oral;
* Speaking fluently in English or French is required. Writing in English is mandatory.

We offer:

* A research position in a dynamic and advanced high-tech environment, working on leading-edge technologies and having many international contacts.

* Funding for 2-3 years, with the possibility to extend it by applying for a Belgian NSF grant.


Application:

Applications should include a detailed resume, copy of grade sheets for B.Sc. and M.Sc. Names and complete addresses of referees are welcome.

Please send applications by email to:

 laurent.jacques@uclouvain.be
 ph.antoine@uclouvain.be

Questions about the subject or the position should be addressed to the same email addresses.


Finally, while most imagers pay specific attention to getting the right light into lenses and then onto the imaging dye, you always are dependent on stray light. Here is an Edmund Optics entry on the subject for reducing stray light. I look at it from a different point of view, maybe painting the edge of the lens other than black provide additional "scrambled" information about the scene. I wonder how that could be used for some compressive sensing work (like the weak compressed sensing concept). By the way if you think that stray light is just a problem we have when designing star trackers, think again, it looks like this is the reason you will not see a white iPhone anytime soon.

Wednesday, October 27, 2010

When Modeling Reality Is Not An Option (The Robust Mathematical Modeling Blog)

Some of you know this but others may not. I sometimes blog about robust mathematical modeling (when modeling reality is not an option is the motto). The reason I say this is because I just wrote an entry there about a workshop I attended last week on issues related to modeling and its pitfalls. One of the issue discussed (the MOX talk) used to be an issue we struggled with in the Excess-Weapons Plutonium disposition program back in the late nineties.  The entry  SCM Talks: Electricity Production Management and the MOX Computational Chain features the fascinating problematic of planning electricity production for France and the computational difficulties stemming from performing experiments and computational calibration exercises outside the real region of operation of a nuclear reactor.  


Tuesday, October 26, 2010

CS: Recovering Compressively Sampled Signals Using Partial Support Information, MDL Sparse coding and dictionary learning, Robust PCA via Outlier Pursuit and more

Today we have a series of papers from arxiv and more:

In this paper we study recovery conditions of weighted $\ell_1$ minimization for signal reconstruction from compressed sensing measurements when partial support information is available. We show that if at least $50%$ of the (partial) support information is accurate, then weighted $\ell_1$ minimization is stable and robust under weaker conditions than the analogous conditions for standard $\ell_1$ minimization. Moreover, weighted $\ell_1$ minimization provides better bounds on the reconstruction error in terms of the measurement noise and the compressibility of the signal to be recovered. We illustrate our results with extensive numerical experiments on synthetic data and real audio and video signals.

Statistical Compressive Sensing of Gaussian Mixture Models by Guoshen Yu, Guillermo Sapiro. The abstract reads:
A new framework of compressive sensing (CS), namely statistical compressive sensing (SCS), that aims at efficiently sampling a collection of signals that follow a statistical distribution and achieving accurate reconstruction on average, is introduced. For signals following a Gaussian distribution, with Gaussian or Bernoulli sensing matrices of O(k) measurements, considerably smaller than the O(k log(N/k)) required by conventional CS, where N is the signal dimension, and with an optimal decoder implemented with linear filtering, significantly faster than the pursuit decoders applied in conventional CS, the error of SCS is shown tightly upper bounded by a constant times the k-best term approximation error, with overwhelming probability. The failure probability is also significantly smaller than that of conventional CS. Stronger yet simpler results further show that for any sensing matrix, the error of Gaussian SCS is upper bounded by a constant times the k-best term approximation with probability one, and the bound constant can be efficiently calculated. For signals following Gaussian mixture models, SCS with a piecewise linear decoder is introduced and shown to produce for real images better results than conventional CS based on sparse models.

The power of sparse signal coding with learned 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 underfitting or overfitting given sets of data, are still not well characterized in the literature. This work aims at filling this gap by means of the Minimum Description Length (MDL) principle -- a well established information-theoretic approach to statistical inference. The resulting framework derives a family of efficient sparse coding and modeling (dictionary learning) algorithms, which by virtue of the MDL principle, are completely parameter free. Furthermore, such framework allows to incorporate additional prior information in the model, such as Markovian dependencies, in a natural way. We demonstrate the performance of the proposed framework with results for image denoising and classification tasks.
Robust PCA via Outlier Pursuit by: Huan Xu, Constantine Caramanis, Sujay Sanghavi. The abstract reads:
Singular Value Decomposition (and Principal Component Analysis) is one of the most widely used techniques for dimensionality reduction: successful and efficiently computable, it is nevertheless plagued by a well-known, well-documented sensitivity to outliers. Recent work has considered the setting where each point has a few arbitrarily corrupted components. Yet, in applications of SVD or PCA such as robust collaborative filtering or bioinformatics, malicious agents, defective genes, or simply corrupted or contaminated experiments may effectively yield entire points that are completely corrupted.
We present an efficient convex optimization-based algorithm we call Outlier Pursuit, that under some mild assumptions on the uncorrupted points (satisfied, e.g., by the standard generative assumption in PCA problems) recovers the exact optimal low-dimensional subspace, and identifies the corrupted points. Such identification of corrupted points that do not conform to the low-dimensional approximation, is of paramount interest in bioinformatics and financial applications, and beyond. Our techniques involve matrix decomposition using nuclear norm minimization, however, our results, setup, and approach, necessarily differ considerably from the existing line of work in matrix completion and matrix decomposition, since we develop an approach to recover the correct column space of the uncorrupted matrix, rather than the exact matrix itself.
Found thanks to Google:
Feasibility of high temporal resolution breast DCE-MRI using compressed sensing theory. by Wang H, Miao Y, Zhou K, Yu Y, Bao S, He Q, Dai Y, Xuan SY, Tarabishy B, Ye Y, Hu J.
PURPOSE: To investigate the feasibility of high temporal resolution breast DCE-MRI using compressed sensing theory.

METHODS: Two experiments were designed to investigate the feasibility of using reference image based compressed sensing (RICS) technique in DCE-MRI of the breast. The first experiment examined the capability of RICS to faithfully reconstruct uptake curves using undersampled data sets extracted from fully sampled clinical breast DCE-MRI data. An average approach and an approach using motion estimation and motion compensation (ME/MC) were implemented to obtain reference images and to evaluate their efficacy in reducing motion related effects. The second experiment, an in vitro phantom study, tested the feasibility of RICS for improving temporal resolution without degrading the spatial resolution.

RESULTS: For the uptake-curve reconstruction experiment, there was a high correlation between uptake curves reconstructed from fully sampled data by Fourier transform and from undersampled data by RICS, indicating high similarity between them. The mean Pearson correlation coefficients for RICS with the ME/MC approach and RICS with the average approach were 0.977 +/- 0.023 and 0.953 +/- 0.031, respectively. The comparisons of final reconstruction results between RICS with the average approach and RICS with the ME/MC approach suggested that the latter was superior to the former in reducing motion related effects. For the in vitro experiment, compared to the fully sampled method, RICS improved the temporal resolution by an acceleration factor of 10 without degrading the spatial resolution.

CONCLUSIONS: The preliminary study demonstrates the feasibility of RICS for faithfully reconstructing uptake curves and improving temporal resolution of breast DCE-MRI without degrading the spatial resolution.


Behind a paywall: Compressive sensing applied to audio signals using higher-order projections and the spatial domain. by Elizabeth Hoppe and Michael Roan. The abstract reads:
Compressive sensing (CS) is a new approach to data acquisition that is receiving much attention in the current literature. The main goal in CS is to accurately reconstruct a signal from a small number of randomly projected basis functions. The CS reconstruction accuracy hinges on the assumption that the signal can be projected into a sparse domain. A majority of the CS research to date has been focused on the application of CS to image processing. There has, however, been very limited research on the application of CS techniques to audio signals focused in two main areas: the use of the frequency and wavelet domains as the sparse signal domain, and the use of the spatial domain to perform compressive beamforming. In this work, two new approaches are examined. The first is the use of the spatial domain to reconstruct signals instead of simply identifying their direction of arrival. The second is the use of higher-order projection techniques (such as principal component analysis) as a sparse domain. This work will apply these techniques to speech signals to examine the ability of CS to reconstruct wide-band audio signals. In addition, the effect of additive noise on the reconstruction accuracy will be examined.

Finally, at Tsinghua, there was a talk last week:

Wireless Sensor Network Group

Title: Compressive Sensing in Wireless Sensor Networks, Surface Coverage in Wireless Sensor Networks

Speaker: Liwen Xu,Xiaohong Hao

Date: 10:00 -- 11:30 Oct 18, 2010

Venue: FIT 1-203

Abstract:

Compressive Sensing in Wireless Sensor Networks

Compressive Sensing (CS) is an emerging theory that is baed on the fact that a relatively small number of random projections of a signal can contain most of its salient information. CS is now successfully applied in the field of image and video compression. It is obvious that the CS is also attractive to Wireless Sensor Networks (WSN). In this talk, several schemes how CS is applied will be introduced, and we will talk about the future of CS in WSN.

Surface Coverage in Wireless Sensor Networks

Coverage is a fundamental problem in Wireless Sensor Networks (WSNs). Existing studies on this topic focus on 2D ideal plane coverage and 3D full space coverage. The 3D surface of a targeted Field of Interest is complex in many real world applications; and yet, existing studies on coverage do not produce practical results. In this paper, we propose a new coverage model called surface coverage. In surface coverage, the targeted Field of Interest is a complex surface in 3D space and sensors can be deployed only on the surface. We show that existing 2D plane coverage is merely a special case of surface coverage. Simulations point out that existing sensor deployment schemes for a 2D plane cannot be directly applied to surface coverage cases. In this paper, we target two problems assuming cases of surface coverage to be true. One, under stochastic deployment, how many sensors are needed to reach a certain expected coverage ratio? Two, if sensor deployment can be planned, what is the optimal deployment strategy with guaranteed full coverage with the least number of sensors? We show that the latter problem is NP-complete and propose three approximation algorithms. We further prove that these algorithms have a provable approximation ratio. We also conduct comprehensive simulations to evaluate the performance of the proposed algorithms.

Image Credit: NASA/JPL/Space Science Institute
W00065872.jpg was taken on October 23, 2010 and received on Earth October 25, 2010. The camera was pointing toward SATURN at approximately 2,451,860 kilometers away, and the image was taken using the CL1 and RED filters.

Sunday, October 24, 2010

CS: The Compressive Mutliplexer for Multi-Channel Compressive Sensing, Limited Feedback For Cognitive Radio Networks, Phase retrieval and a job

When I read this presentation entitled Compressed sensing with coherent and redundant dictionaries by Deanna Needell, I nearly spilled my coffee when I got to the verbose slide 21....


and the more to the point slide 22.


I know... I am a nerd. Another example for overcomplete dictionary includes voice as illustrated in a recent entry in Bob Sturm's blog entry (and comments). The audio folks are not prepared to use CS hardware because they are already getting good data from their sometimes expensive microphones. I am of the view that a CS based hardware would produce other kind of data than just quaint sound recording.



The recently developed compressive sensing (CS) framework enables the design of sub-Nyquist analog-to-digital converters. Several architectures have been proposed for the acquisition of sparse signals in large swaths of bandwidth. In this paper we consider a more flexible multi-channel signal model consisting of several discontiguous channels where the occupancy of the combined bandwidth of the channels is sparse. We introduce a new compressive acquisition architecture, the compressive multiplexer (CMUX), to sample such signals. We demonstrate that our architecture is CS-feasible and suggest a simple implementation with numerous practical advantages.
In this paper, we consider the downlink of a cognitive radio network where a cognitive base station serves multiple cognitive users on the same frequency band as a group of primary transceivers. The cognitive base station uses an orthogonal scheduling scheme (TDMA/FDMA) to serve its users. For this purpose, the base station is interested in acquiring an estimate of the interference (from the primary network) power at each of its cognitive receivers as a measure of channel quality. This can be surely achieved if we allow for the feedback (from the cognitive receivers to the cognitive base station) bandwidth to scale linearly in the number of cognitive receivers, but in densely populated networks, the cost of such an acquisition might be too high. This leads us to the question of whether we can do better in terms of bandwidth efficiency. We observe that in many scenarios – that are common in practice – where the primary network exhibits sparse changes in transmit powers from one scheduling instant to the next, it is possible to acquire this interference state with only a logarithmic scaling in feedback bandwidth. More specifically, in cognitive networks where the channels are solely determined by the positions of nodes, we can use compressed sensing to recover the interference state. In addition to being a first application of compressed sensing in the domain of limited feedback, to the best of our knowledge, this paper makes a key mathematical contribution concerning the favourable sensing properties of path-loss matrices that are composed of nonzero mean, dependent random entries. Finally, we numerically study the robustness properties of the least absolute shrinkage and selection operator (LASSO), a popular recovery algorithm, under two error models through simulations. The first model considers a varying amount of error added to all entries of the sensing matrix. The second one, a more adversarial model, considers a large amount of error added to only a fraction of the entries of the sensing matrix that are chosen uniformly at random. Simulation results establish that the LASSO recovery algorithm is robust to imperfect channel knowledge.


Behind a paywall:

Phase retrieval of diffraction from highly strained crystals by Marcus C. Newton, Ross Harder, Xiaojing Huang, Gang Xiong, and Ian K. Robinson. The abstract reads:
An important application of phase retrieval methods is to invert coherent x-ray diffraction measurements to obtain real-space images of nanoscale crystals. The phase information is currently recovered from reciprocal-space amplitude measurements by the application of iterative projective algorithms that solve the nonlinear and nonconvex optimization problem. Various algorithms have been developed each of which apply constraints in real and reciprocal space on the reconstructed object. In general, these methods rely on experimental data that is oversampled above the Nyquist frequency. To date, support-based methods have worked well, but are less successful for highly strained structures, defined as those which contain (real-space) phase information outside the range of ±π/2. As a direct result the acquired experimental data is, in general, inadvertently subsampled below the Nyquist frequency. In recent years, a new theory of “compressive sensing” has emerged, which dictates that an appropriately subsampled (or compressed) signal can be recovered exactly through iterative reconstruction and various routes to minimizing the ℓ1 norm or total variation in that signal. This has proven effective in solving several classes of convex optimization problems. Here we report on a “density-modification” phase reconstruction algorithm that applies the principles of compressive sensing to solve the nonconvex phase retrieval problem for highly strained crystalline materials. The application of a nonlinear operator in real-space minimizes the ℓ1 norm of the amplitude by a promotion-penalization (or “propenal”) operation that confines the density bandwidth. This was found to significantly aid in the reconstruction of highly strained nanocrystals. We show how this method is able to successfully reconstruct phase information that otherwise could not be recovered.


Finally, here is a job announcement at King's College, London:

Research Associate Division of Imaging Sciences & Biomedical EngineeringG6/MRE/530/10-HH21/11/2010
SummaryWe are seeking 1 post-doctoral Research Associate for 2 years to participate in a large multi-centre EPSRC funded programme grant (Intelligent imaging: motion, form and function across scale (EPSRC EP/H046410/1), a collaboration between KCL, UCL, Imperial College and The Institute of Cancer Research. The programme focuses on a multidisciplinary medical imaging approach, with the aim of providing clinicians the information they really need. It involves modelling, image processing and registration, and medical imaging physics. This post is part of a work package on improved image reconstruction, in particular MRI reconstruction including motion correction. It will be based in the Division of Imaging Sciences and Biomedical Engineering, a newly created structure in the School of Medicine at King's College London, part of King's Health Partners. It is situated on the 4th floor Lambeth Wing, St Thomas Hospital, one of the leading research hospitals in London. The Division is a unique group made of clinicians, physicists, mathematicians, chemists, biologists, and engineers working on translational research, and it has strong links with industrial partners such as Philips.

The aim of this post is to develop compressed sensing techniques for motion correction in MRI, but with a view of widening applications within the context of intelligent imaging as described by the grant proposal. More generally, the project might involve techniques beyond standard compressed sensing enabling additional prior information to be used. The compressed sensing might be used to measure motion and provide input for other motion correction developed in the lab, or even maybe directly in a generalised motion and under sampling reconstruction framework. In addition, collaboration with novel acquisition and sampling developments for example using parallel transmit techniques are likely.
DetailsSome experience in compressed sensing and MRI is required. The ideal candidate would have good knowledge of cardiac MRI, in particular aspects of acquisition and reconstruction, as well as general image reconstruction and processing techniques. Some experience of parallel MRI and parallel transmit MRI is desirable. This post is part of a large programme grant involving multiple imaging modalities, disciplines (maths, physics, medicine, biology) and institutions (UCL, KCL, Imperial College, Oxford), thus the candidate should also have the personal qualities required to work in such an environment.
SalaryThe salary will be on grade 6: from £30,747 to £33,599 plus £2323 London allowance per annum, depending on experience.
Post durationtwo years
ContactFor an information pack please see further details. Please quote reference G6/MRE/530/10-HH when applying and in all correspondence. Closing date: 17 October 2010 Creating a world-leading Academic Health Sciences Centre. Equality of Opportunity is College Policy.
Further detailsPlease see related Word document

Printfriendly