My name is Igor Carron
View Igor Carron's profile on linkedin

Thursday, February 16, 2012

Les Cameras Aleatoires

The presentation is here.: Les Cameras Aleatoires.


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.
By at No comments:
labels:

A small op-ed and Advanced Matrix Factorization This Week

I have decided to change the name of the LinkedIn Group on Matrix Factorization to Advanced Matrix Factorization. It is not just a question of branding, we need to send a signal that current matrix factorization techniques mentioned in that group and here are not your grandfather's matrix factorizations. In other words, we don't care about SVDs, we care about very large scale SVDs who can deal with all kinds of "unexpected" issues, we don't care about a slight improvement of NMF, we care about knowing why NMF works and how it can be extended once and for all and when we denoise the endoscopic videos made at Fukushima, it's not because we have better schemes to denoise, it's because we want to use the noise to evaluate radiation levels....We want to make sense of it all.



I noted some interesting entries in Danny Bickson's blog:: 

Since Danny's blog is very relevant to some of the issues of Large Scale Matrix Factorization, I have decided to add his feed directly into the discussions on the LinkedIn Advanced Matrix Factorization group which now boasts more than 180 members. 

Also found on the interweb, the following papers, enjoy:

High-dimensional tensors or multi-way data are becoming prevalent in areas such as biomedical imaging, chemometrics, networking and bibliometrics. Traditional approaches to finding lower dimensional representations of tensor data include flattening the data and applying matrix factorizations such as principal components analysis (PCA) or employing tensor decompositions such as the CANDECOMP / PARAFAC (CP) and Tucker decompositions. The former can lose important structure in the data, while the latter Higher-Order PCA (HOPCA) methods can be problematic in high-dimensions with many irrelevant features. We introduce frameworks for sparse tensor factorizations or Sparse HOPCA based on heuristic algorithmic approaches and by solving penalized optimization problems related to the CP decomposition. Extensions of these approaches lead to methods for general regularized tensor factorizations, multi-way Functional HOPCA and generalizations of HOPCA for structured data. We illustrate the utility of our methods for dimension reduction, feature selection, and signal recovery on simulated data and multi-dimensional microarrays and functional MRIs.

HOPCA and Sparse HOPCA will be downloadable from  http://www.stat.rice.edu/~gallen/software.html at some point in time. When they are, I'll feature them in the Matrix Factorization Jungle page.



We consider the problem of estimating a rank-one matrix in Gaussian noise under a probabilistic model for the left and right factors of the matrix. The probabilistic model can impose constraints on the factors including sparsity and positivity that arise commonly in learning problems. We propose a simple iterative procedure that reduces the problem to a sequence of scalar estimation computations. The method is similar to approximate message passing techniques based on Gaussian approximations of loopy belief propagation that have been used recently in compressed sensing. Leveraging analysis methods by Bayati and Montanari, we show that the asymptotic behavior of the estimates from the proposed iterative procedure is described by a simple scalar equivalent model, where the distribution of the estimates is identical to certain scalar estimates of the variables in Gaussian noise. Moreover, the effective Gaussian noise level is described by a set of state evolution equations. The proposed method thus provides a computationally simple and general method for rank-one estimation problems with a precise analysis in certain high-dimensional settings.


In this paper, we propose a study of performance of the channel estimation using LS, MMSE, LMMSE and Lr-LMMSE algorithms in OFDM (Orthogonal Frequency Division Multiplexing) system which, as known suffers from the time variation of the channel under high mobility conditions, using block pilot insertion. The loss of sub channel orthogonality leads to inter-carrier interference (ICI). Using many algorithms for channel estimation, we will show that, for a 16- QAM modulation, the LMMSE algorithm performs well to achieve this estimation but when the SNR (Signal Noise Rate) is high, the four algorithms (LS, MMSE, LMMSE and Lr-LMMSE) perform similarly, this is not always the case for another scheme of modulation. We will improve also the mean squared error for these algorithms. It will be illustrious in this paper that the LMMSE algorithm performs well with the block- pilot insertion as well as its low rank version which behave very good even when the size of FFT is very high.

We investigate the problem of signal transduction via a descriptive analysis of the spatial organization of the complement of proteins exerting a certain function within a cellular compartment. We propose a scheme to assign a numerical value to individual proteins in a protein interaction network by means of a simple optimization algorithm. We test our procedure against datasets focusing on the proteomes in the neurite and soma compartments.

The ADI iteration is closely related to the rational Krylov projection methods for constructing low rank approximations to the solution of Sylvester equation. In this paper we show that the ADI and rational Krylov approximations are in fact equivalent when a special choice of shifts are employed in both methods. We will call these shifts pseudo H2-optimal shifts. These shifts are also optimal in the sense that for the Lyapunov equation, they yield a residual which is orthogonal to the rational Krylov projection subspace. Via several examples, we show that the pseudo H2-optimal shifts consistently yield nearly optimal low rank approximations to the solutions of the Lyapunov equations.

This paper studies the models of minimizing $||x||_1+1/(2\alpha)||x||_2^2$ where $x$ is a vector, as well as those of minimizing $||X||_*+1/(2\alpha)||X||_F^2$ where $X$ is a matrix and $||X||_*$ and $||X||_F$ are the nuclear and Frobenius norms of $X$, respectively. We show that they can efficiently recover sparse vectors and low-rank matrices. In particular, they enjoy exact and stable recovery guarantees similar to those known for minimizing $||x||_1$ and $||X||_*$ under the conditions on the sensing operator such as its null-space property, restricted isometry property, spherical section property, or RIPless property. To recover a (nearly) sparse vector $x^0$, minimizing $||x||_1+1/(2\alpha)||x||_2^2$ returns (nearly) the same solution as minimizing $||x||_1$ almost whenever $\alpha\ge 10||x^0||_\infty$. The same relation also holds between minimizing $||X||_*+1/(2\alpha)||X||_F^2$ and minimizing $||X||_*$ for recovering a (nearly) low-rank matrix $X^0$, if $\alpha\ge 10||X^0||_2$. Furthermore, we show that the linearized Bregman algorithm for minimizing $||x||_1+1/(2\alpha)||x||_2^2$ subject to $Ax=b$ enjoys global linear convergence as long as a nonzero solution exists, and we give an explicit rate of convergence. The convergence property does not require a solution solution or any properties on $A$. To our knowledge, this is the best known global convergence result for first-order sparse optimization algorithms.

In this paper, we study the problem of high-dimensional approximately low-rank covariance matrix estimation with missing observations. We propose a simple procedure computationally tractable in high-dimension and that does not require imputation of the missing data. We establish non-asymptotic sparsity oracle inequalities for the estimation of the covariance matrix with the Frobenius and spectral norms, valid for any setting of the sample size and the dimension of the observations. We further establish minimax lower bounds showing that our rates are minimax optimal up to a logarithmic factor.

This paper considers the problem of completing a matrix with many missing entries under the assumption that the columns of the matrix belong to a union of multiple low-rank subspaces. This generalizes the standard low-rank matrix completion problem to situations in which the matrix rank can be quite high or even full rank. Since the columns belong to a union of subspaces, this problem may also be viewed as a missing-data version of the subspace clustering problem. Let X be an n x N matrix whose (complete) columns lie in a union of at most k subspaces, each of rank <= r < n, and assume N >> kn. The main result of the paper shows that under mild assumptions each column of X can be perfectly recovered with high probability from an incomplete version so long as at least CrNlog^2(n) entries of X are observed uniformly at random, with C>1 a constant depending on the usual incoherence conditions, the geometrical arrangement of subspaces, and the distribution of columns over the subspaces. The result is illustrated with numerical experiments and an application to Internet distance matrix completion and topology identification.
The knowledge of end-to-end network distances is essential to many Internet applications. As active probing of all pairwise distances is infeasible in large-scale networks, a natural idea is to measure a few pairs and to predict the other ones without actually measuring them. This paper formulates the distance prediction problem as matrix completion where unknown entries of an incomplete matrix of pairwise distances are to be predicted. The problem is solvable because strong correlations among network distances exist and cause the constructed distance matrix to be low rank. The new formulation circumvents the well-known drawbacks of existing approaches based on Euclidean embedding. 
A new algorithm, so-called Decentralized Matrix Factorization by Stochastic Gradient Descent (DMFSGD), is proposed to solve the network distance prediction problem. By letting network nodes exchange messages with each other, the algorithm is fully decentralized and only requires each node to collect and to process local measurements, with neither explicit matrix constructions nor special nodes such as landmarks and central servers. In addition, we compared comprehensively matrix factorization and Euclidean embedding to demonstrate the suitability of the former on network distance prediction. We further studied the incorporation of a robust loss function and of non-negativity constraints. Extensive experiments on various publicly-available datasets of network delays show not only the scalability and the accuracy of our approach but also its usability in real Internet applications.
By at No comments:
labels: , , , , ,

Wednesday, February 15, 2012

"Les Caméras Aléatoires" and Nuit Blanche's Mailbag

Tomorrow night (Thursday), I'll be speaking at Dorkbot at La Cantine and it'll be at 8:00 pm. The title of the talk will be "Les Caméras Aléatoires". The crowd is not made up of specialists but some of the folks  are interesting hardware hackers and artists and so I'll be pitching the random lens imager. If you want to have a bird's eye view of the subject, you might consider attending. I think I'll be speaking in French (depending on the crowd).


Today Gabriel Peyre:and Dick Gordon: provided some insights in a simplified approach to TV regularization and the use of FBP in hardware (CT scanners). While I realize that FBP does not work in 3D, there ought to be a simple case made that connects FBP to compressive sensing simply. At the very least, additional insight could definitely be gained from taking into account the findings of the intriguing paper A variant on the compressed sensing of Emmanuel Candes by Yves Meyer and Basarab Matei, but that's just me. Without further wait here are the following insights:


From Gabriel Peyre:

Hi everybody,
... I have finally taken some time to explain how to solve TV regularization without using primal-dual-schemes:
(it is applied to segmentation, but you can apply the same method to inverse problems as well).
If you find any error or typo, please let me know!
For another approach to avoid using primal dual schemes:
....

From Dick Gordon:


Dear Igor, 
There’s a new iterative CT algorithm in the mill: SAFIRE (Sinogram Affirmed Iterative Reconstruction), which I came across in: Siemens (2012). Flash Speed. Lowest Dose. SOMATOM Definition Flash  
It’s described in: 
Nelson, R.C., S. Feuerlein & D.T. Boll (2011). New iterative reconstruction techniques for cardiovascular computed tomography: How do they work, and what are the advantages and disadvantages? Journal of Cardiovascular Computed Tomography 5(5), 286-292.
Abstract. The radiation doses associated with diagnostic CT scans has recently come under scrutiny. In the process of developing protocols with lower doses, it has become apparent that images reconstructed with a filtered back projection (FBP) technique are often inadequate. Although very fast and robust, FBP images are prone to high noise, streak artifacts and poor low contrast detectability in low dose situations. Manufacturers of CT equipment have responded to this limitation by developing new image reconstruction techniques that derive more information from the data set. These techniques are based on the use of maximum likelihood algorithms and are referred to at iterative reconstructions. This iterative process can be used on the slice data alone, a combination of raw and slice data or on the raw data alone. The latter approach, which is referred to as model based iterative reconstruction, is the most computationally demanding as it models the entire process, from the shape of the focal spot on the anode, the shape of the emerging x-ray beam, the three-dimensional interaction of the beam with the voxel in the patient and the two-dimensional interaction of the beam with the detector. This article discusses the fundamentals of iterative reconstruction techniques, the pros and cons of the various manufacturer approaches and specific applications, especially to cardiovascular CT. 
Beister, M., D. Kolditz & W.A. Kalender (2012). Iterative reconstruction methods in X-ray CT. Physica Medica, http://dx.doi.org/10.1016/j.ejmp.2012.1001.1003.
Abstract: Iterative reconstruction (IR) methods have recently re-emerged in transmission x-ray computed tomography (CT). They were successfully used in the early years of CT, but given up when the amount of measured data increased because of the higher computational demands of IR compared to analytical methods. The availability of large computational capacities in normal workstations and the ongoing efforts towards lower doses in CT have changed the situation; IR has become a hot topic for all major vendors of clinical CT systems in the past 5 years.
This review strives to provide information on IR methods and aims at interested physicists and physicians already active in the field of CT. We give an overview on the terminology used and an introduction to the most important algorithmic concepts including references for further reading. As a practical example, details on a model-based iterative reconstruction algorithm implemented on a modern graphics adapter (GPU) are presented, followed by application examples for several dedicated CT scanners in order to demonstrate the performance and potential of iterative reconstruction methods. Finally, some general thoughts regarding the advantages and disadvantages of IR methods as well as open points for research in this field are discussed. 
Nothing explicitly on compressive sensing in these. SAFIRE is basically iteration of FBP (Fourier backprojection), and so will suffer the same problems that FBP has with sparse data. Nevertheless, the fact that it has been embedded in a commercial CT scanner and received FDA approval for 50% dose reduction may invigorate the search for sparse CT algorithms that retain image quality while further reducing patient dose...... 
Yours, -Dick
Dr. Richard (Dick) Gordon
Theoretical Biologist, Embryogenesis Center
Gulf Specimen Marine Laboratory (http://www.gulfspecimen.org) 
By at No comments:
labels: , , , ,

Tuesday, February 14, 2012

Compressive Sensing This Week.

Today we have some good news for sensor networks, two papers on analysis type of approaches, manifold signal processing, compressive binary search, a search for the sparse elements of the nullspace and more. Enjoy!


Performance Analysis of $\ell_1$-synthesis with Coherent Frames by Yulong Liu, Shidong Li, Tiebin Mi. The abstract reads:
Signals with sparse representations in frames comprise a much more realistic model of nature, it is therefore highly desirable to extend the compressed sensing methodology to redundant dictionaries (or frames) as opposed to orthonormal bases only. In the generalized setting, the standard approach to recover the signal is known as $\ell_1$-synthesis (or Basis Pursuit). In this paper, we present the performance analysis of this approach in which the dictionary may be highly - and even perfectly - correlated. Our results do not depend on an accurate recovery of the coefficients. We demonstrate the validity of the results via several experiments.


Note on RIP-based Co-sparse Analysis by Lianlin Li. The abstract reads:
Over the past years, there are increasing interests in recovering the signals from undersampling data where such signals are sparse under some orthogonal dictionary or tight framework, which is referred to be sparse synthetic model. More recently, its counterpart, i.e., the sparse analysis model, has also attracted researcher's attentions where many practical signals which are sparse in the truly redundant dictionary are concerned. This short paper presents important complement to the results in existing literatures for treating sparse analysis model. Firstly, we give the natural generalization of well-known restricted isometry property (RIP) to deal with sparse analysis model, where the truly arbitrary incoherent dictionary is considered. Secondly, we studied the theoretical guarantee for the accurate recovery of signal which is sparse in general redundant dictionaries through solving l1-norm sparsity-promoted optimization problem. This work shows not only that compressed sensing is viable in the context of sparse analysis, but also that accurate recovery is possible via solving l1-minimization problem.

Signal Recovery on Incoherent Manifolds by Chinmay Hegde, Richard G. Baraniuk. The abstract reads:
Suppose that we observe noisy linear measurements of an unknown signal that can be modeled as the sum of two component signals, each of which arises from a nonlinear sub-manifold of a high dimensional ambient space. We introduce SPIN, a first order projected gradient method to recover the signal components. Despite the nonconvex nature of the recovery problem and the possibility of underdetermined measurements, SPIN provably recovers the signal components, provided that the signal manifolds are incoherent and that the measurement operator satisfies a certain restricted isometry property. SPIN significantly extends the scope of current recovery models and algorithms for low dimensional linear inverse problems and matches (or exceeds) the current state of the art in terms of performance.

Compressive binary search by Mark A. Davenport, Ery Arias-Castro. The abstract reads:
In this paper we consider the problem of locating a nonzero entry in a high-dimensional vector from possibly adaptive linear measurements. We consider a recursive bisection method which we dub the compressive binary search and show that it improves on what any nonadaptive method can achieve. We establish a non-asymptotic bound that applies to all methods, regardless of their computational complexity. Combined, these results show that the compressive binary search is within a double logarithmic factor of the optimal performance.

Achievable Angles Between two Compressed Sparse Vectors Under Norm/Distance Constraints Imposed by the Restricted Isometry Property: A Plane Geometry Approach by Ling-Hua Chang, Jwo-Yuh Wu. The abstract reads:
The angle between two compressed sparse vectors subject to the norm/distance constraints imposed by the restricted isometry property (RIP) of the sensing matrix plays a crucial role in the studies of many compressive sensing (CS) problems. Assuming that (i) u and v are two sparse vectors separated by an angle thetha, and (ii) the sensing matrix Phi satisfies RIP, this paper is aimed at analytically characterizing the achievable angles between Phi*u and Phi*v. Motivated by geometric interpretations of RIP and with the aid of the well-known law of cosines, we propose a plane geometry based formulation for the study of the considered problem. It is shown that all the RIP-induced norm/distance constraints on Phi*u and Phi*v can be jointly depicted via a simple geometric diagram in the two-dimensional plane. This allows for a joint analysis of all the considered algebraic constraints from a geometric perspective. By conducting plane geometry analyses based on the constructed diagram, closed-form formulae for the maximal and minimal achievable angles are derived. Computer simulations confirm that the proposed solution is tighter than an existing algebraic-based estimate derived using the polarization identity. The obtained results are used to derive a tighter restricted isometry constant of structured sensing matrices of a certain kind, to wit, those in the form of a product of an orthogonal projection matrix and a random sensing matrix. Follow-up applications to three CS problems, namely, compressed-domain interference cancellation, RIP-based analysis of the orthogonal matching pursuit algorithm, and the study of democratic nature of random sensing matrices are investigated.


D-ADMM: A Communication-Efficient Distributed Algorithm For Separable Optimization by João F. C. Mota, João M. F. Xavier, Pedro M. Q. Aguiar, Markus Püschel. The abstract reads:
We propose a distributed algorithm, named D-ADMM, for solving separable optimization problems in networks of interconnected nodes or agents. In a separable optimization problem, the cost function is the sum of all the agents' private cost functions, and the constraint set is the intersection of all the agents' private constraint sets. We require the private cost function and constraint set of a node to be known by that node only, during and before the execution of the algorithm. The application of our algorithm is illustrated with problems from signal processing and control, namely average consensus, compressed sensing, and support vector machines. It is well known that communicating in distributed environments is the most energy/time-demanding operation. Thus, algorithms using less communications are more prone to make networks live longer, e.g., sensor networks, or to execute faster, e.g., in supercomputing platforms. Through simulations for several network types and problems, we show that our algorithm requires less communications than the state-of-the-art algorithms.


Sensitivity Considerations in Compressed Sensing by Louis L. Scharf, Edwin K. P. Chong, Ali Pezeshki. The abstract reads:
In [1]–[4], we considered the question of basis mismatch in compressive sensing. Our motivation was to study the effect of mismatch between the mathematical basis (or frame) in which a signal was assumed to be sparse and the physical basis in which the signal was actually sparse. We were motivated by the problem of inverting a complex space-time radar image for the field of complex scatterers that produced the image. In this case there is no apriori known basis in which the image is actually sparse, as radar scatterers do not usually agree to place their ranges and Dopplers on any apriori agreed sampling grid. The consequence is that sparsity in the physical basis is not maintained in the mathematical basis, and a sparse inversion in the mathematical basis or frame does not match up with an inversion for the field in the physical basis. In [1]–[3], this effect was quantified with theorem statements about sensitivity to basis mismatch and with numerical examples for inverting time series records for their sparse set of damped complex exponential modes. These inversions were compared unfavorably to inversions using fancy linear prediction. In [4] and this paper, we continue these investigations by comparing the performance of sparse inversions of sparse images, using apriori selected frames that are mismatched to the physical basis, and by computing the Fisher information matrix for compressions of images that are sparse in a physical basis.

Saliency-guided compressive sensing approach to efficient laser range measurement by Shimon Schwartz, Alexander Wong, David A. Clausi. The abstract reads:
The acquisition of laser range measurements can be a time consuming process for situations where high spatial resolution is required. As such, optimizing the acquisition mechanism is of high importance for many range measurement applications. Acquiring such data through a dynamically small subset of measurement locations can address this problem. In such a case, the measured information can be regarded as incomplete, which necessitates the application of special reconstruction tools to recover the original data set. The reconstruction can be performed based on the concept of sparse signal representation. Recovering signals and images from their sub-Nyquist measurements forms the core idea of compressive sensing (CS). A new saliency-guided CS-based algorithm for improving the reconstruction of range image from sparse laser range measurements has been developed. This system samples the object of interest through an optimized probability density function derived based on saliency rather than a uniform random distribution. Particularly, we demonstrate a saliency-guided sampling method for simultaneously sensing and coding range image, which requires less than half the samples needed by conventional CS while maintaining the same reconstruction performance, or alternatively reconstruct range image using the same number of samples as conventional CS with a 16 dB improvement in signal-to-noise ratio. For example, to achieve a reconstruction SNR of 30 dB, the saliency-guided approach required 30% of the samples in compari-
son to the standard CS approach that required 90% of the samples in order to achieve similar performance.



Multi-Level Error-Resilient Neural Networks with Learning by Amir Hesam Salavati, Amin Karbasi. The abstract reads:
The problem of neural network association is to retrieve a previously memorized pattern from its noisy version using a network of neurons. An ideal neural network should include three components simultaneously: a learning algorithm, a large pattern retrieval capacity and resilience against noise. Prior works in this area usually improve one or two aspects at the cost of the third. Our work takes a step forward in closing this gap. More specifically, we show that by forcing natural constraints on the set of learning patterns, we can drastically improve the retrieval capacity of our neural network. Moreover, we devise a learning algorithm whose role is to learn those patterns satisfying the above mentioned constraints. Finally we show that our neural network can cope with a fair amount of noise.


Image Credit: NASA/JPL/Space Science Institute
N00181356.jpg was taken on February 12, 2012 and received on Earth February 12, 2012. The camera was pointing toward TITAN at approximately 3,695,492 kilometers away, and the image was taken using the CL1 and MT1 filters. 


By at 1 comment:
labels: , , , ,

Monday, February 13, 2012

Interesting Links and Octopus vs Cancer

Here are a few items of interest:




I remember in High School, we had this discussion with our philosophy professor about the intelligence of animals. His take was that there really was no intelligence that came even close to that of the humans. Most of us were flabbergasted, because we felt that his point of view was disingenuous at best as it reflected more his need to continue on being a professor of philosophy than from any actual knowledge of the situation. Take for instance the case of the octopus. The following video is in french but it should not be too hard to understand (except when the aquarium folks tell the story that these octopuses besides spying on them, literally go from one aquarium to the next, go hunting for some fish there and then come back in their home aquarium).




Poulpe thalassa 005_5'44 se ballader, dévisser- 1er st résoudre 1 pb nouveau Vidéo Tad-coz sélectionnée dans Animaux


A species that spies on us and display learning abilities beyond that of chimps, that would certainly qualify as getting close to human learning. Why am I talking about this ? I just read this entry on David Rosenthal's blog entitled Tide Pools and Terrorists and couldn't shake off the similarities between underestimating cancer cells (Cancer is just as deadly as it was 50 years ago. Here’s why that’s about to change.) and how smart octopuses are. The tentacles part is also striking. 





Source: National Cancer Institute.


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.
By at 2 comments:
labels: , , , ,

Friday, February 10, 2012

Looking through walls and around corners with incoherent light: Wide-field real-time imaging through scattering media [updated]

Ori Katz, one of the authors of the Ghost Imaging compressive Sensing paper just sent me the following:


Dear Igor
.... We have just posted a work on the arXiv which I thought (hoped;-) might interest you: 
In this work we are showing that one can use scattered incoherent light for imaging objects hidden behind/reflected-from a scattering medium (e.g. a 'wall'). We do this by using the technique of high-resolution wavefront-shaping with SLMs. In short, we 'learn' the scattering properties of the medium and then apply the inverse phase-pattern to make the 'wall' either transparent or mirror-like. All the best,
Ori



Imaging with optical resolution through highly scattering media is a long sought-after goal with important applications in deep tissue imaging. Although being the focus of numerous works, this goal was considered impractical until recently. Adaptive-optics techniques which are effective in correcting weak wavefront aberrations, were deemed inadequate for turbid samples, where complex speckle patterns arise and light is scattered to a large number of modes that greatly exceeds the number of degrees of control. This conception changed after the demonstration of focusing coherent light through turbid media by wavefront-shaping, using a spatial-light-modulator (SLM). Here we show that wavefront-shaping enables widefield real-time imaging through scattering media with both coherent or incoherent illumination, in transmission and reflection. In contrast to the recently introduced schemes for imaging through turbid media, our technique does not require coherent sources, interferometric detection, raster scanning, or off-line image reconstruction. Our results bring wavefront-shaping closer to practical applications, and realize the vision of looking 'through walls' and 'around corners'.

This is outstanding.and here is why. I initially asked Sylvain Gigan on the matter to make sure I did not misunderstand too much. As you probably recall Sylvain is a one of the author of Measuring the Transmission Matrix in Optics : An Approach to the Study and Control of Light Propagation in Disordered Media. He told me ( i.e. all inaccuracies are mine) that the paper is beautiful because in part, it is using incoherent light. I then, specifically asked him how, in this paper, the authors seemed to be finding the measurement matrix faster than say in his own experiment (see above). Sylvain pointed out that they use the memory effect so that after say learning the first row of the measurement matrix, this memory effect allows them to automatically construct other neighboring rows. In short, this is not unlike the coded aperture systems mentioned yesterday in Learning a Circulant Matrix by Yangyang Xu, Wotao Yin, Susan Chen and Stanley Osher. Indeed the coded aperture systems are an instance of Toeplitz measurement matrices that are really parametrically dependent upon a low dimensional set of variables. This work seems to work only for very thin "walls" and hence it is ideal for looking around corners as reflection is really a little like a thin wall assumption. 

I then asked Ori another set of questions:


What sort of optimization do you go through to get the SLM to be providing a point on the CCD ? Is it some sort of convex optimization or more like a monte carlo or greedy algorithm ? How long is this process ?

We are running a genetic algorithm optimization which looks for the optimal phase pattern that will maximize the intensity of the point source on a selected camera pixel. In each optimization step (generation) the algorithm test 30 different patterns and keeps the best ones for generating the phase-patterns for the next step.  We typically ran a few hundreds of such generations before stopping

It looks like the incoherence of the source is really helping you in that process as it enables everything around the point to be imaged the same. Do you have any idea of how far this imaging can go, i.e. How far away from the point, do you get to image the scene ( I am not sure I am saying this right) ?

The incoherent illumination indeed helps in generating a smooth image (it doesn't really matters in the optimization procedure). The limit for the field-of-view around the pre-optimized point source position is dictated by what people call the 'optical memory-effect' - the maximum angle for which the single phase-pattern correction still holds. When looking through optically-thick multiply scattering media (e.g. a wall) this angle is given by: theta~lambda/L, where L is the thickness of the medium and lambda is the wavelength. When looking at light reflected from a random medium (our Fig.3), the angular field of view will be theta~lambda/L_s, where L_s is the scattering mean-free-path for light in the medium (~ the penetration depth of the light into the wall). In our experiment, we had a angular field of view of theta ~5 mrad, (equivalent to an image of size ~2mm at a distance of 40cm from the wall) in reflection geometry, and something around 15 mrad in the transmission experiments . For an object out of the 'memory effect' angle, the correction intensity falls exponentially.


Thank you Ori  for the beautiful paper and attendant explanations and Sylvain for the initial insight.



  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.
By at No comments:
labels: , , ,

Thursday, February 09, 2012

Compressive Sensing This Week

Here are some of the finds for this week in compressive sensing:



First here is a paper of interest for someone interested in calibratiing a coded aperture imager:


LEARNING A CIRCULANT SENSING MATRIX  by YANGYANG XU, WOTAO YIN, SUSAN CHEN, AND STANLEY OSHER. The abstract reads:
In signal acquisition, Toeplitz and circulant matrices are widely used as sensing operators since they can be easily or even naturally realized in various applications. For compressive sensing, recent work has used random Toeplitz and circulant sensing matrices and proved their e ciency in theory, by computer simulations, as well as through physical optical experiments. Motivated by recent work [7], we propose models to optimize a circulant sensint matrix. Given the dictionary of the signal(s) to be sensed, the optimized circulant sensing matrix is more e ective than a randomly generated circulant sensing matrix, and even a Gaussian random sensing matrix. In addition, we test learning the circulant sensing matrix and the nonparametric dictionary altogether and obtain even better performance on encoding and decoding test signals. We demonstrate these results using both synthetic sparse signals and real images.



ROBUST 1-BIT COMPRESSED SENSING AND SPARSE LOGISTIC REGRESSION: A CONVEX PROGRAMMING APPROACH by YANIV PLAN AND ROMAN VERSHYNIN. The abstract reads:
Abstract. This paper develops theoretical results regarding noisy 1-bit compressed sensing and
sparse binomial regression. We demonstrate that a single convex program gives an accurate estimate of the signal, or coefficient vector, for both of these models. We show that an s-sparse signal in Rn can be accurately estimated from m = O(s log(n=s)) single-bit measurements using a simple convex program. This remains true even if almost half of the measurements are randomly flipped. Worst-case (adversarial) noise can also be accounted for, and uniform results that hold for all sparse inputs are derived as well. In the terminology of sparse logistic regression, we show that O(s log(n=s)) Bernoulli trials are sufficient to estimate a coe cient vector in Rn which is approximately s-sparse. Moreover, the same convex program works for virtually all generalized linear models, in which the link function may be unknown. To our knowledge, these are the first results that tie together the theory of sparse logistic regression to 1-bit compressed sensing. Our results apply to general signal structures aside from sparsity; one only needs to know the size of the set K where signals reside. The size is given by the mean width of K, a computable quantity whose square serves as a robust extension of the dimension.

Compressive sensing (CS) provides a general signal acquisition framework that enables the reconstruction of sparse signals from a small number of linear measurements. To reduce video-encoder complexity, we present a CS-based video compression scheme. Modern video-encoder complexity arises mainly from the transformcoding and motion-estimation blocks. In our proposed scheme, we eliminate these blocks from the encoder, which achieves compression by merely taking a few linear measurements of each image in a video sequence. To guarantee stable reconstruction of the video sequence from only a few measurements, the decoder must effectively exploit the inherent spatial and temporal redundancies in a video sequence. To leverage these redundancies, we consider a motion-adaptive linear dynamical model for videos. Recovery process involves solving an `1-regularized optimization problem, which iteratively updates estimates for the video frames and motion within adjacent frames.

The poster is here.


FPGA-Accelerated 3D Reconstruction Using Compressive Sensing by Jianwen Chen, Jason Cong, Ming Yan and Yi Zou. The abstract reads:
The radiation dose associated with computerized tomography (CT) is significant. Optimization-based iterative reconstruction approaches, e.g., compressive sensing provide ways to reduce the radiation exposure, without sacrificing image quality. However, the computational requirement such algorithms is much higher than that of the conventional Filtered Back Projection (FBP) reconstruction algorithm. This paper describes an FPGA implementation of one important iterative kernel called EM, which is the major computation kernel of a recent EM+TV reconstruction algorithm. We show that a hybrid approach (CPU+GPU+FPGA) can deliver a better performance and energy efficiency than GPU-only solutions, providing 13X boost of throughput than a dual-core CPU implementation.


Implementation of Sub-Nyquist Sampling System  Based on Compressed Sensing  by Xiaoyan Zhuang, Yijiu Zhao, Li Wang, Houjun Wang. The abstract reads:
This paper describes the development of a sub-Nyquist sampling system that can digitize high-speed signals using a low-speed analog to digital converter (ADC). The system is implemented by a field programmable gate array (FPGA), and it is possible to make change to the equivalent sampling frequency according to the practical applications. As an application of the compressed sensing (CS) theory, for the spectrally sparse analog signal sampling, the proposed system has the potential to break though the constraint of Shannon theorem and the bandwidth barrier of state-of-the-art ADCs. Potential limitations of the applicability of CS-based sampling system are also discussed. Experimental results show that this sampling system is able to capture spectrally sparse analog signal at an equivalent sampling rate of 500 MHz while sampled at a rate of no more than 100 MHz physically.




Lightweight remote imaging systems have been increasingly used in surveillance and reconnaissance. Nevertheless, the limited power, processing and bandwidth resources is a major issue for the existing solutions, not well addressed by the standard video compression techniques. On the one hand, the MPEGx family achieves a balance between the reconstruction quality and the required bit-rate by exploiting potential intra- and interframe redundancies at the encoder, but at the cost of increased memory and processing demands. On the other hand, the M-JPEG approach consists of a computationally efficient encoding process, with the drawback of resulting in much higher bit-rates. In this paper, we cope with the growing compression ratios, required for all remote imaging applications, by exploiting the inherent property of compressive sensing (CS), acting simultaneously as a sensing and compression framework. The proposed compressive video sensing (CVS) system incorporates the advantages of a very simple CS-based encoding process, while putting the main computational burden at the decoder combining the efficiency of a motion compensation procedure for the extraction of inter-frame correlations, along with an additional super-resolution step to enhance the quality of reconstructed frames. The experimental results reveal a significant improvement of the reconstruction quality when compared with M-JPEG, at equal or even lower bit-rates.


Augmented ℓ1 and Nuclear-Norm Models with a Globally Linearly Convergent Algorithm by Ming-Jun Lai, Wotao Yin. The abstract reads:

This paper studies the models of minimizing kxk1 +12αkxk22 where x is a vector, as well as those of minimizing kXk∗ +12αkXk2F where X is a matrix and kXk∗ and kXkF are the nuclear and Frobenius norms of X, respectively. We show that they can efficiently recover sparse vectors and low-rank matrices. In particular, they enjoy exact and stable recovery guarantees similar to those known for minimizing kxk1 and kXk∗ under the conditions on the sensing operator such as its null-space property, restricted isometry property, spherical section property, or “RIPless” property. To recover a (nearly) sparse vector x0, minimizing kxk1 +12αkxk2 returns (nearly) the same solution as minimizing kxk1 almost wheneverα ≥ 10kx0k∞. The same relation also holds between minimizing kXk∗ +12αkXk2F and minimizing kXk∗ for recovering a (nearly) low-rank matrix X0, if α ≥ 10kX0k2. Furthermore, we show that the linearized Bregman algorithm for minimizing kxk1 +12αkxk22 subject to Ax = b enjoys global linear convergence as long as a nonzero solution exists, and we give an explicit rate of convergence. The convergence property does not require a solution solution or any properties on A. To our knowledge, this is the best known global convergence result for first-order sparse optimization algorithms.



Achievable Angles Between two Compressed Sparse Vectors Under Norm/Distance Constraints Imposed by the Restricted Isometry Property: A Plane Geometry Approach by Ling-Hua Chang, Jwo-Yuh Wu. The abstract reads:
The angle between two compressed sparse vectors subject to the norm/distance constraints imposed by the restricted isometry property (RIP) of the sensing matrix plays a crucial role in the studies of many compressive sensing (CS) problems. Assuming that (i) u and v are two sparse vectors separated by an angle thetha, and (ii) the sensing matrix Phi satisfies RIP, this paper is aimed at analytically characterizing the achievable angles between Phi*u and Phi*v. Motivated by geometric interpretations of RIP and with the aid of the well-known law of cosines, we propose a plane geometry based formulation for the study of the considered problem. It is shown that all the RIP-induced norm/distance constraints on Phi*u and Phi*v can be jointly depicted via a simple geometric diagram in the two-dimensional plane. This allows for a joint analysis of all the considered algebraic constraints from a geometric perspective. By conducting plane geometry analyses based on the constructed diagram, closed-form formulae for the maximal and minimal achievable angles are derived. Computer simulations confirm that the proposed solution is tighter than an existing algebraic-based estimate derived using the polarization identity. The obtained results are used to derive a tighter restricted isometry constant of structured sensing matrices of a certain kind, to wit, those in the form of a product of an orthogonal projection matrix and a random sensing matrix. Follow-up applications to three CS problems, namely, compressed-domain interference cancellation, RIP-based analysis of the orthogonal matching pursuit algorithm, and the study of democratic nature of random sensing matrices are investigated.

The road to deterministic matrices with the restricted isometry property by Afonso S. Bandeira, Matthew Fickus, Dustin G. Mixon, Percy Wong. The abstract reads:
The restricted isometry property (RIP) is a well-known matrix condition that provides state-of-the-art reconstruction guarantees for compressed sensing. While random matrices are known to satisfy this property with high probability, deterministic constructions have found less success. In this paper, we consider various techniques for demonstrating RIP deterministically, some popular and some novel, and we evaluate their performance. In evaluating some techniques, we apply random matrix theory and inadvertently find a simple alternative proof that certain random matrices are RIP. Later, we propose a particular class of matrices as candidates for being RIP, namely, equiangular tight frames (ETFs). Using the known correspondence between real ETFs and strongly regular graphs, we investigate certain combinatorial implications of a real ETF being RIP. Specifically, we give probabilistic intuition for a new bound on the clique number of Paley graphs of prime order, and we conjecture that the corresponding ETFs are RIP in a manner similar to random matrices.



Finite Frames for Sparse Signal Processing by Waheed U. Bajwa and Ali Pezeshki. The abstract reads:
Abstract Over the last decade, considerable progress has been made towards developing new signal processing methods to manage the deluge of data caused by advances in sensing, imaging, storage, and computing technologies. Most of these methods are based on a simple but fundamental observation. That is, highdimensional data sets are typically highly redundant and live on low-dimensional manifolds or subspaces. This means that the collected data can often be represented in a sparse or parsimonious way in a suitably selected finite frame. This observation has also led to the development of a new sensing paradigm, called compressed sensing, which shows that high-dimensional data sets can often be reconstructed, with high fidelity, from only a small number of measurements. Finite frames play a central role in the design and analysis of both sparse representations and compressed sensing methods. In this chapter, we highlight this role primarily in the context of compressed sensing for estimation, recovery, support detection, regression, and detection of sparse signals. The recurring theme is that frames with small spectral norm and/or small worst-case coherence, average coherence, or sum coherence are well-suited for making measurements of sparse signals.



DICTIONARY LEARNING OF CONVOLVED SIGNALS by Daniele Barchiesi and Mark D. Plumbley. The abstract reads:
Assuming that a set of source signals is sparsely representable in a given dictionary, we show how their sparse recovery fails whenever we can only measure a convolved observation of them. Starting from this motivation, we develop a block coordinate descent method which aims to learn a convolved dictionary and provide a sparse representation of the observed signals with small residual norm. We compare the proposed approach to the K-SVD dictionary learning algorithm and show through numerical experiment on synthetic signals that, provided some conditions on the problem data, our technique converges in a fixed number of iterations to a sparse representation with smaller residual norm


The implementation of the k-t FOCUSS web address is now here at: Dynamic MRI

New Update
The matlab source codes for cartesian k-t FOCUSS with ME/MC (motion estimation and compensation) and radial k-t FOCUSS are now downloadable. Please see "Download and File Description" below.


k-t FOCUSS
We developed k-t FOCUSS algorithm which is optimal from compressed sensing point of view. The basic concept of k-t FOCUSS starts from compressed sensing theory. According to compressed sensing theory, it is possible to reconstruct original signal from severely reduced sampling ratio which break Nyquist sampling limit. Therefore, this theory is getting huge interests in MRI area, because it is greatly required to reconstruct artifact free images from very sparse measurements to improve temporal resolution. There are some constraints to exploit this concept. From compressed sensing perspective, the aliasing pattern due to down sampling should incoherently appear. Therefore, the random sampling pattern is preferred. Furthermore, the original signal should be able to be sparsely transformed or compressed. And then, L1 minimization of the sparse signal is required. From these basic assumptions, we found that FOCUSS is a very suitable reconstruction algorithm. FOCUSS is originally designed to reconstruct sparse signal. Furthermore, L1 optimization is achieved by successively solving weighted L2 optimization problem, which can be easily implemented. From these advantages, we successfully developed k-t FOCUSS which reconstructs high spatio-temporal resolution of dynamic images such as a heart beating.



Finally, we have a workshop in Germany:

1st International Workshop on Compressed Sensing applied to Radar
Radar/SAR awaits Compressed SensingCompressed sensing (CS) techniques offer a framework for the detection and allocation of sparse signals with a reduced number of samples. Today, modern radar systems operate with high bandwidths - demanding high sample rates according to the Shannon-Nyquist theorem - and a huge number of single elements for phased array antennas. Often only a small amount of target parameters is the final output, raising the question, whether CS could be a good means to reduce data size, complexity, weight, power consumption and costs of radar systems. The amount of publications addressing the application of CS to radar is still limited, leaving open a number of questions.
ScopeThe scope of the proposed International Workshop is to bring experts of Compressed Sensing together to explore the state-of-the-art in development of such techniques in the different nations and for the different applications and to turn out its advantages or possible drawbacks compared to classical solutions. The workshop program will include invited speeches from distinguished experts as well as contributed talks.
Key aspectsContributions are expected on, but not limited to:
  • CS for pulse compression
  • CS for synthetic aperture radar (SAR)
  • CS for SAR tomography
  • CS for active and passive airspace surveillance
  • CS for moving target detection
  • CS for radar clutter suppression
  • CS for MIMO architectures
  • Hardware aspects of CS
  • CS for radiometry and sonar
  • Mathematical aspects of CS in radar
  • CS in statistical signal processing
ParticipantsThe workshop will provide a forum for experts, research engineers, and scientists working in the area of Compressive Sensing and Radar/SAR.
They get insight into the current research trends, innovative sensor technology, associated signal processing, and the subsequent data processing and transmission steps.
Veranstaltungsort
Bonn, Germany
Datum
14.5.2012 - 16.5.2012
Organisation
Fraunhofer-Institut für Hochfrequenzphysik und Radartechnik FHR
Sprache
Englisch
1st International Workshop on Compressed Sensing applied to Radar1st International Workshop on Compressed Sensing applied to Radar(elserv.fhr.fraunhofer.de)







Image Credit: NASA/JPL/Space Science Institute
Full-Res: N00181212.jpg
N00181212.jpg was taken on February 06, 2012 and received on Earth February 07, 2012. The camera was pointing toward JANUS, and the image was taken using the CL1 and CL2 filters.




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.
By at No comments:
labels: , , ,
Subscribe to: Posts (Atom)

Printfriendly