Tuesday, June 21, 2011

Two Solvers: R1Magic and YALL1 Group



I just came across a CS solver written in R as shown in this presentation: Compressive Sampling with R: A Tutorial by Mehmet Suzen. The R1Magic package is here. A reference manual is here.

YALL1 now include a group sparsity solving capability. Let us look at what he can do. From the webpage:

YALL1 package now includes:
  • YALL1 Basic
  • , a solver for sparse reconstruction: Version 1.3, Apr 07, 2011.
  • YALL1 Group
  • , a solver for group/joint sparse reconstruction: Version 1.0, June 09, 2011. Wiki
YALL1 Basic
solves the following L1-minimization problems:
(BP) min ||Wx||w,1 s.t. Ax = b
(L1/L1) min ||Wx||w,1 + (1/ν)||Ax - b||1 (L1/L2) min ||Wx||w,1 + (1/2ρ)||Ax - b||22 (L1/L2con) min ||Wx||w,1, s.t. ||Ax - b||2 <= δ
(BP+) min ||x||w,1 s.t. Ax = b and x >= 0
(L1/L1+) min ||x||w,1 + (1/ν)||Ax - b||1 s.t. x >= 0
(L1/L2+) min ||x||w,1 + (1/2ρ)||Ax - b||22 s.t. x >= 0
(L1/L2con+) min ||x||w,1, s.t. ||Ax - b||2 <= δ, x >= 0
where
  • A
  •  is an m-by-n matrix with m << n,
  • the solution x (or its representation Wx) is supposed to be (approximately) sparse,
  • the data and solution can be real or complex, (If complex, then no non-negativity constraint is allowed)
  • a unitary sparsifying basis W is optional,
  • the 1-norm can be optionally weighted by a nonnegative vector w.
Go to discussions and Q&As.
Supported Features
  • Multiple types of A
  • explicit matrix
  • ensembles of fast transforms such as FFT, DCT, wavelets
  • Both real and complex data
  • Both sparse and compressible signals
  • Non-negative signals
YALL1 Group
The group sparsity code solves the following model
(GroupBP) min sumi wi ||x_gi||2 s.t. Ax = b
where g1, g2, … are groups of coordinates and w1,w2, … are their weights.
Joint sparsity is a special case of group sparsity for recovering X = [x1,x2, ..., xl] where the xi‘s share a common sparse support.
(JointBP) min sumi wi ||Xi,:||2 s.t. AX = B.
Supported Features
  • Multiple types of A
  • explicit matrix
  • ensembles of fast transforms such as FFT, DCT, wavelets
  • general function handle
  • Groups can overlap
  • The union of groups does not need to cover all coordinates
  • Easy to modify for the support of complex numbers and your signals
Contributors
Yin Zhang*, Wei Deng, Junfeng Yang, and Wotao Yin.
* The original author of YALL1 (beta 1 – 6).
Tech report
YALL1 Basic: Alternating Direction Algorithms for L1 Problems in Compressive Sensing, Rice CAAM Report TR09-37, 2009.
YALL1 Group/Joint Sparsity: Group Sparse Optimization by Alternating Direction Method, Rice CAAM Report TR11-06, 2011.
Download
YALL1 is now open-source. It is distributed under the terms of the GNU General Public License. [Proceed to the download page]


Credit Video: ESA/DLR/FU Berlin (G. Neukum), via the Planetary Society blog.
Phobos ( a moon of Mars) slips past Jupiter, On June 1 2011, Mars express watched as Phobos (the inner and larger of Mars' two moons) slipped past distant Jupiter. Mars Express is studying Phobos to help the Russian Phobos-Grunt mission prepare to land on the moon and grab a sample for return to Earth. Credit: ESA/DLR/FU Berlin (G. Neukum)

Monday, June 20, 2011

Compressive Sensing Coded Aperture in Space and Weak Lensing

There were many interesting presentations at  Statistical Challenges in Modern Astronomy V. But I'll present today only the three most relevant to Compressive sensing. 

The first one was the presentation of Richard Baraniuk that featured some of his recent work (third part of the presentation) that featured a pro-cons approach to compressive sensing. Then there was a presentation by Jean-Luc Stark who leads the Sparse Astro group at CEA in France that focuses on sparsity issues in astronomy. This group is interesting in the french research setting as it has its hands in influencing more directly some of the hardware that will eventually go into space.The presentation is here. I don't know if this is just me but the presentations are painful to download. Some of the slides are inserted below and present some older work and new ones:


Inpainting the COROT signals.

Results of using a compressive sensing encoding from the PACS camera on Herschel and comparison with the results of the official data pipeline (we have already talked about this before).


I think I mentioned this one a while back, but it looks like the plan is becoming more precise. The French-Chinese Gamma Ray Burst camera seems to be headed toward a compressive sensing design for its coded aperture. Wow, a real CS hardware in space (not just a software encoder).

Also in the same conference, there is the presentation of Adrienne Leonard, Francois-Xavier Dupe, and Jean-Luc Starck on Improving weak lensing reconstructions in 3D using sparsity that shows current work connecting compressive sensing and weak lensing (we mentioned it recently).

Friday, June 17, 2011

Compact Signatures for High-speed Interest Point Description and Matching

How did I miss this ? I don't know but I fumbled big time since I am very interested in the subject:



Prominent feature point descriptors such as SIFT and SURF allow reliable real-time matching but at a computational cost that limits the number of points that can be handled on PCs, and even more on less powerful mobile devices. A recently proposed technique that relies on statistical classification to compute signatures has the potential to be much faster but at the cost of using very large amounts of memory, which makes it impractical for implementation
on low-memory devices. In this paper, we show that we can exploit the sparseness of these signatures to compact them, speed up the computation, and drastically reduce memory usage. We base our approach on Compressive Sensing theory. We also highlight its effectiveness by incorporating it into two very different SLAM packages and demonstrating substantial performance increases.

Besides the obvious leap forward that compressive sensing allows for SLAM, here is something else I noted:

"...Remarkably, as will be shown in the experimental section, using either a Random Ortho-Projection or a PCA projection yields virtually the same results. This sheds light on the inner workings of the many methods [16], which perform PCA dimensionality reduction of SIFT-style descriptors. It suggests that their success owes more to the underlying sparsity of these descriptors than to PCA itself...."

If you do recall, this is the reason I wrote "Shouldn't We Call It "Sparse Sensing" or "Sparsity Sensing" instead ?". Slowly we are realizing that some empirical findings may be rooted in sparsity.


Michael Calonder's defended his PhD thesis in October 2010  Robust, High-speed Interest Point Matching For Real-Time Applications. Some of the folks who were involved in that paper work at Willow Garage, a very interesting company. An RSS feed for their news is here, their Twitter feed is here.

Compressive Sensing Reader's Mailbag of the Week.

Jim Fowler sent me the following:

Hi Igor,
I would like to let you know of a journal article that we will have appearing soon in IEEE Transactions on Image Processing. The details are: J. E. Fowler and Q. Du, “Anomaly Detection and Reconstruction from Random Projections,” IEEE Transactions on Image Processing, to appear.
Abstract:
Compressed-sensing methodology typically employs random projections simultaneously with signal acquisition to accomplish dimensionality reduction within a sensor device. The effect of such random projections on the preservation of anomalous data is investigated. The popular RX anomaly detector is derived for the case in which global anomalies are to be identified directly in the random-projection domain, and it is determined via both random simulation as well as empirical observation that strongly anomalous vectors are likely to be identifiable by the projection-domain RX detector even in low-dimensional projections. Finally, a reconstruction procedure for hyperspectral imagery is developed wherein projection-domain anomaly detection is employed to partition the dataset, permitting anomaly and normal pixel classes to be reconstructed separately in order to improve the representation of the anomaly pixels.
Best Regards,
-Jim

Thanks Jim

Zoltán Szabó who was featured earlier because of his paper (Online Group-Structured Dictionary Learning) sent me the following:

Dear Igor,
I've made the Matlab code available on my homepage ("http://nipg.inf.elte.hu/szzoli"), the direct link to the code is
"http://people.inf.elte.hu/nipg/people/szabo_zoltan/repo/code/OSDL/OSDL_Matlab_package_version1.rar",
Zoltan

Thanks Zoltán

Gabriel Cristobal wanted us to know about a new book:

Igor,
This is just to inform you that we recently published the book "Optical and Digital Image Processing-Fundamentals and Applications" that it's available from Amazon and other retailers. See the book' webpage: http://www.odipbook.info
As you can see from the table of contents, the book includes two chapters on CS: Ch. 22&23.
Also Ch. 23 mention your blog. Perhaps you can include the book in your reference store.
Best regards

Thanks Gabriel. I have indeed added it to the Nuit Blanche reference store on compressive sensing (Page 1 and page 2)







Laurent Duval finally made the following announcement for a PhD thesis at IFP

2011-R11-3
Représentations parcimonieuses pour la restauration et l'analyse quantitative de champs d'ondes en sismiques
Lieu : IFP Energies nouvelles Rueil-Malmaison
Promoteur : Laurent Duval
Postuler : laurent.duval@ifpen.fr
Du fait de la complexité des champs d'ondes présents dans les données sismiques, de nombreux outils centraux au traitement du signal (en déconvolution, en décompositions en ondelettes) ont bénéficié des avancées dans ce domaine. Ces données présentent notamment des caractéristiques à mi-chemin entre signaux 1-D et images, qui ont produit une quantité d'outils monodimensionnels ou plus directionnels. Cependant des perturbations comme les ondes de surface, les multiples ou ondes de tubes défient encore les traitements standard. Récemment, des techniques provenant du traitement d'images (tenseurs de structure, ondelettes complexes ou curvelets) ont provoqué un certain intérêt pour des applications de filtrage ou de migration des données sismiques. Il apparaît en effet que l'usage de trames multidimensionnelles légèrement redondantes, possédant une bonne localisation tempsfréquence offrent une directionalité locale qui permet d'approcher fidèlement les données par quelques coefficients importants. Ces représentations parcimonieuses sont une des clés de la réussite de traitement ultérieurs, notamment dans un environnement de bruits importants. Le travail de thèse proposé vise à développer une série de méthodes, inspirées des développement récents en traitement d'images, permettant de répondre à des besoins de filtrage de bruits aléatoires, de bruits cohérents et de déconvolution de données par un opérateur variable, tout en préservant un certain nombre d'attributs temps-fréquence standard.
Le candidat s'intéressera particulièrement à un attribut complémentaire : la phase. Celle-ci peut être obtenue par le calcul de la "trace complexe", avatar du signal analytique
[Gabor1946]. Le coeur de la thèse portera sur l'estimation robuste de la phase, dans un contexte multi-échelle, et sur le développement d'algorithmes de restauration la préservant, pour des signaux sismiques. Le candidat travaillera au sein de l'équipe de traitement du signal, en contact rapproché avec les géophysiciens et le partenaire industriel. Dans la mesure où ce sujet suscite depuis peu l'intérêt de la communauté du traitement d'images, le candidat bénéficiera d'une atmosphère de recherche active, avec un des applications potentielles en dehors du monde de la géophysique.



Not found in the mailbag but a job announcement I saw a while ago in Nature:

Design, Implementation and Measurement of a Analog-to-Information Converters Based on Compressive Sensing. : Italy
Employer:
Università degli Studi di Ferrara
Location:
Italy
Type:
Other
Posted:
June 07, 2011
Expires:
June 29, 2011
Requisition number:
Euraxess-euraxess-fellowships-13962
Science jobs from Università degli Studi di Ferrara: job description

Scientific supervisor:Prof. Gianluca Setti Location of activity: Dipartimento di Ingegneria Durata: 12 months Warning: The formal application requires filling a specific form available online at the web site of the University of Ferrara: http://www.unife.it/ateneo/uffici/ripartizione-risorse-umane/ufficio-selezione-personale/assegni/

Thursday, June 16, 2011

Don't tell me you did not prepare for this.

Mahesh kindly asked the following question yesterday:

@IgorCarron What is the context of your latest blog post, if I may ask?

I wondered a little bit if the detail of the context mattered and then I decided against providing more light to it. Not because there is something exceptional to it but rather because it doesn't matter. Next time you are at one of these meetings, challenge yourself to be that one person in the room who will ask a question at the end of each of the talks. You did not cross an ocean, get padded by friendly customs officials, exposed yourself to new bugs, traveled thousands of miles to not ask that question or make that comment and start that conversation. 

Wednesday, June 15, 2011

Damn you, Laurent, Damn you!

The choosing of an important problem a la Hamming can be deeply embedded within many different reasons, some of them might be deeply emotional.

When writing your thesis or when you were eight and discovering the Collatz conjecture, somebody enlightened your world. That problem, that riddle, became the most important in the world. But then as everything in life  you had to move on, sometimes without making a mark or being content and left whoever put you in that spot to continue thinking about it on their own, you had to move on. Several years later you serendipitously stumble again on that one problem. Here it is, this old friend is news again either because somebody has solved it or you have since learned new tools. You know the problem is not as urgent as it used to be, but then again you don't care. You may even warmly resent the person who brought it back in your spotlight. But you are happy taking on this old friend. You can now reconnect with the pack of people who worked with you on this years ago and tell them you may have solved it. Some of the people may have gone onto other shores. It doesn't matter, you know that it is now your responsibility to take a new stab at it.

For the ones that are not there anymore, you watch the clear skies and mumble: "Recall that discussion we had twenty years ago, well I think there is a way to solve it simply...Dude, I got your back"

Credit photo: The Shawshank Redemption.

Compressive Sensing Literature This Week (part two).


Alexandre Thiery has a blog entry on compressive sensing. Zhilin talks about some Misunderstandings on Sparse Bayesian Learning (SBL) for Compressed Sensing (2), while Bob is implementing CMP in MPTK and  Pardis talks about the Paper of the Day (Po'D): Encoding vs. Training with Sparse Coding Edition. The Google also found the following papers on the interwebs:

Compressive sampling is a technique of recovering sparse N-dimensional signals from low-dimensional sketches, i.e., their linear images in Rm; m N: The main question associated with this technique is construction of linear operators that allow faithful recovery of the signal from its sketch. The most frequently used sufficient condition for robust recovery is the near-isometry property of the operator when restricted to k-sparse signals. We study 1-matrices of dimensions m N that satisfy the restricted isometry property of order k (k-RIP). As our main set of results, we describe a general method of constructing sampling matrices for which a statistical version of k-RIP holds. We also show that m N matrices with k-RIP and m = O(k2log N) can be constructed with time complexity O(k2N log N):

Poisson Compressed Sensing by Rebecca Willett and Maxim Raginsky. The abstract reads:
Compressed sensing has profound implications for the design of new imaging and network systems, particularly when physical and economic limitations require that these systems be as small and inexpensive as possible. However, several aspects of compressed sensing theory are inapplicable to real-world systems in which noise is signal-dependent and unbounded. In this work we discuss some of the key theoretical challenges associated with the application of compressed sensing to practical hardware systems and develop performance bounds for compressed sensing in the presence of Poisson noise. We develop two novel sensing paradigms, based on either pseudo-random dense sensing matrices or expander graphs, which satisfy physical feasibility constraints. In these settings, as the overall intensity of the underlying signal increases, an upper bound on the reconstruction error decays at an appropriate rate (depending on the compressibility of the signal), but for a fixed signal intensity, the error bound actually grows with the number of measurements or sensors. This surprising fact is both proved theoretically and justified based on physical intuition.


Dynamic Range and Compressive Sensing Acquisition Receivers by John Treichler, Mark Davenport, Jason Laska, and Richard Baraniuk. The abstract reads:
Compressive sensing (CS) exploits the sparsity present in many signal environments to reduce the number of measure- ments needed for digital acquisition and processing. We have previously introduced the concept and feasibility of using CS techniques to build a wideband signal acquisition systems. This paper extends that work to examine such a receiver’s performance as a function of several key design parameters. In particular we show that that the system noise figure is predictably degraded as the subsampling implicit in CS is made more aggressive. Conversely we show that the dynamic range of a CS-based system can be substantially improved as the subsampling factor grows. The ability to control these aspects of performance provides an engineer new degrees of freedom in the design of wideband acquisition systems. A specific practical example, a multi-collector emitter geoloca- tion system, is included to illustrate that point.


Network Tomography via Compressed Sensing by Mohammad H. Firooz, Sumit Roy. The abstract reads:

In network tomography, we seek to infer link status parameters (such as delay) inside a network through end-toend probe sending between (external) boundary nodes. The main challenge here is to estimate link-level attributes from end-to-end measurements. In this paper by using the idea of combinatorial compressed sensing, we provide conditions on network routing matrix under which it is possible to estimate links delay from end-to-end delay measurements. We also provide an upper-bound on the estimation error. Moreover, for a given network, we show how to design its routing matrix to achieve the minimum number of probes needed to be sent in order to estimate delay of the links inside the network.

On the web but no preprint:


Image Credit: NASA/JPL/Space Science Institute, N00172726.jpg was taken on June 11, 2011 and received on Earth June 13, 2011. The camera was pointing toward JANUS, and the image was taken using the CL1 and CL2 filters.

Tuesday, June 14, 2011

Spring-Summer School Paris IHP 2011

From Djalil's blog, here is a Summer school announcement with program. I added it to the list of Compressive Sensing meetings:


Spring-Summer School 
June 20-21-22, 2011
 
Random matrices - Stochastic geometry - Compressed sensing

UPE-MLV ANR IHP
This Spring-Summer School will consists in series of accessible lectures (9 hours in total for each speaker) on random matrices, stochastic geometry and compressed sensing.

Speakers

  • Jared Tanner (U. Edinburgh, UK)
    Stochastic Geometry and Random Matrix Theory in Compressed Sensing
    Stochastic geometry and random matrix theory can be used to model and analyse the efficacy of a new paradigm in signal processing, compressed sensing. This new perspective shows that if a signal is sufficiently simple, it can be acquired at a rate proportional to its information content rather than the worst case rate dictated by a larger ambient space containing it. These lectures will show how this phenomenon can be modelled using stochastic geometry, and will also show how standard eigen-analysis in random matrix theory can give similar results.
  • Roman Vershynin (U. Michigan, USA)
    Introduction to the non-asymptotic analysis of random matrices
    This is a mini-course on basic non-asymptotic methods and concepts in random matrix theory. We will develop several tools for the analysis of the extreme singular values of random matrices with independent rows or columns. Many of these methods sprung off from the development of geometric functional analysis in the 1970-2000's. They have applications in several fields, most notably in theoretical computer science, statistics and signal processing. Two applications will be discussed: for the problem of estimating covariance matrices in statistics, and for validating probabilistic constructions of measurement matrices in compressed sensing.

Audience

This school is addressed to non-specialists: participation of postdocs and PhD students is strongly encouraged.

Program and schedule

Institut Henri Poincaré, Paris, from June 20 to June 22, 2011. Amphi Darboux 9:30-18:00.
A continental breakfast (buffet) will be available at 8:45 in the IHP hall.
Social dinner on Monday 20 evening (probable restaurant).
M20T21W22
09:30-10:30RVRVRV
11:00-13:00RVRVRV
14:30-15:30JTJTJT
16:00-18:00JTJTJT

Organizers

D. Chafaï & A. Pajor (U. Paris-Est Marne-la-Vallée), A. Tsybakov (U. Pierre et Marie Curie Paris VI & CREST)

Sponsors

Monday, June 13, 2011

Compressive Sensing Literature This Week.

Today we have quite a few papers and presentations. Enjoy!



We propose a framework for compressive sensing of images with local geometric features. Speci cally, let x 2 RN be an N-pixel image, where each pixel p has value xp. The image is acquired by computing the measurement vector Ax, where A is an m N measurement matrix for some m N. The goal is then to design the matrix A and recovery algorithm which, given Ax, returns an approximation to x. In this paper we investigate this problem for the case where x consists of a small number (k) of \local geometric objects" (e.g., stars in an image of a sky), plus noise. We construct a matrix A and recovery algorithm with the following features: (i) the number of measurements m is O(k logk N), which undercuts currently known schemes that achieve m = O(k log(N=k)) (ii) the matrix A is ultra-sparse, which is important for hardware considerations (iii) the recovery algorithm is fast and runs in time sub-linear in N. We also present a comprehensive study of an application of our algorithm to a problem in satellite navigation.

Of note is the excerpt on adapting this scheme to star trackers:
...Computation power on a satellite is substantially lower than that of a low end laptop, and given that the entire acquisition has to happen in .1 to 2 seconds, it seems unlikely that any algorithm linear or near linear in N is going to be practical. Finally, we note that all plot lines in the results could be improved by a more thorough implementation of a star identification algorithm....

No Kidding!

The Master of Engineering thesis on which this paper is based on is A Compressive Sensing Algorithm for Attitude Determination by Rishi Gupta. The abstract reads:
We propose a framework for compressive sensing of images with local distinguishable objects, such as stars, and apply it to solve a problem in celestial navigation. Speci cally, let x 2 RN be an N- pixel image, consisting of a small number of local distinguishable objects plus noise. Our goal is to design an m N measurement matrix A with m N, such that we can recover an approximation to x from the measurements Ax. We construct a matrix A and recovery algorithm with the following properties: (i) if there are k objects, the number of measurements m is O((k log N)=(log k)), undercutting the best known bound of O(k log(N=k)) (ii) the matrix A is ultra-sparse, which is important when the signal is weak relative to the noise, and (iii) the recovery algorithm is empirically fast and runs in time sub-linear in N. We also present a comprehensive study of the application of our algorithm to attitude determination, or finding one's orientation in space. Spacecraft typically use cameras to acquire an image of the sky, and then identify stars in the image to compute their orientation. Taking pictures is very expensive for small spacecraft, since camera sensors use a lot of power. Our algorithm optically compresses the image before it reaches the camera's array of pixels, reducing the number of sensors that are required.

The algorithm is here or will be ( Rishi tells me it will be there in about ten days). Thanks Rishi.


Nonparametric Bayesian methods are considered for recovery of imagery based upon compressive, incomplete and/or noisy measurements. A truncated beta-Bernoulli process is employed to infer an appropriate dictionary for the data under test, and also for image recovery. In the context of compressive sensing, significant improvements in image recovery are manifested using learned dictionaries, relative to using standard orthonormal image expansions. The compressive-measurement projections are also optimized for the learned dictionary. Additionally, we consider simpler (incomplete) measurements, defined by measuring a subset of image pixels, selected uniformly at random. Spatial inter-relationships within imagery are exploited through use of the Dirichlet and probit stick-breaking processes. Several example results are presented, with comparisons to other methods in the literature.

This paper establishes information-theoretic limits in estimating a finite field low-rank matrix given random linear measurements of it. These linear measurements are obtained by taking inner products of the unknown matrix with random sensing matrices in the finite field. Necessary and sufficient conditions on the number of measurements required are provided. It is shown that these conditions are sharp. The reliability function of the minimum-rank decoder is also derived by appealing to de Caen’s lower bound on the probability of a union. The sufficient conditions also hold in the case where the sensing matrices are sparse – a scenario that may be amenable to faster decoding. More precisely, it is shown that if the n n-sensing matrices contain, on average, (nlog n) entries, the number of measurements required is the same as that when the sensing matrices are dense and contain entries drawn uniformly at random from the field. Analogies are drawn between the above results and rank-metric codes in the coding theory literature. In particular, we derive minimum (rank) distance properties of equiprobable and sparse rank-metric codes. These distance properties provide a precise geometric interpretation of the fact that the sparse ensemble requires as few measurements as the dense one. Finally, we provide a non-exhaustive procedure to search for the unknown low-rank matrix.


This note presents a unified analysis of the recovery of simple objects from random linear measurements. When the linear functionals are Gaussian, we show that an s-sparse vector in Rn can be efficiently recovered from 2s log n measurements with high probability and a rank r, n n matrix can be efficiently recovered from r(6n 5r) with high probability. For sparse vectors, this is within an additive factor of the best known nonasymptotic bounds. For low-rank matrices, this matches the best known bounds. We present a parallel analysis for block sparse vectors obtaining similarly tight bounds. In the case of sparse and block sparse signals, we additionally demonstrate that our bounds are only slightly weakened when the measurement map is a random sign matrix. Our results are based on analyzing a particular dual point which certifies optimality conditions of the respective convex programming problem. Our calculations rely only on standard large deviation inequalities and our analysis is self-contained.



The application of compressive sampling to radio astronomy I: Deconvolution by Feng Li, Tim J. Cornwell, Frank de Hoog. The abstract read:
Compressive sampling is a new paradigm for sampling, based on sparseness of signals or signal representations. It is much less restrictive than Nyquist-Shannon sampling theory and thus explains and systematises the widespread experience that methods such as the H\"ogbom CLEAN can violate the Nyquist-Shannon sampling requirements. In this paper, a CS-based deconvolution method for extended sources is introduced. This method can reconstruct both point sources and extended sources (using the isotropic undecimated wavelet transform as a basis function for the reconstruction step). We compare this CS-based deconvolution method with two CLEAN-based deconvolution methods: the H\"ogbom CLEAN and the multiscale CLEAN. This new method shows the best performance in deconvolving extended sources for both uniform and natural weighting of the sampled visibilities. Both visual and numerical results of the comparison are provided.

The application of compressive sampling to radio astronomy II: Faraday rotation measure synthesis by Feng Li, Tim J. Cornwell, Frank de Hoog. The abstract reads:
Faraday rotation measure (RM) synthesis is an important tool to study and analyze galactic and extra-galactic magnetic fields. Since there is a Fourier relation between the Faraday dispersion function and the polarized radio emission, full reconstruction of the dispersion function requires knowledge of the polarized radio emission at both positive and negative square wavelengths $\lambda^2$. However, one can only make observations for $\lambda^2 > 0$. Furthermore observations are possible only for a limited range of wavelengths. Thus reconstructing the Faraday dispersion function from these limited measurements is ill-conditioned. In this paper, we propose three new reconstruction algorithms for RM synthesis based upon compressive sensing/sampling (CS). These algorithms are designed to be appropriate for Faraday thin sources only, thick sources only, and mixed sources respectively. Both visual and numerical results show that the new RM synthesis methods provide superior reconstructions of both magnitude and phase information than RM-CLEAN


Large-Scale Convex Minimization with a Low-Rank Constraint by Shai Shalev-Shwartz, Alon Gonen, Ohad Shamir. The abstract reads:
We address the problem of minimizing a convex function over the space of large matrices with low rank. While this optimization problem is hard in general, we propose an efficient greedy algorithm and derive its formal approximation guarantees. Each iteration of the algorithm involves (approximately) finding the left and right singular vectors corresponding to the largest singular value of a certain matrix, which can be calculated in linear time. This leads to an algorithm which can scale to large matrices arising in several applications such as matrix completion for collaborative filtering and robust low rank matrix approximation.


Random matrices are widely used in sparse recovery problems, and the relevant properties of matrices with i.i.d. entries are well understood. The current paper discusses the recently introduced Restricted Eigenvalue (RE) condition, which is among the most general assumptions on the matrix, guaranteeing recovery. We prove a reduction principle showing that the RE condition can be guaranteed by checking the restricted isometry on a certain family of low-dimensional subspaces. This principle allows us to establish the RE condition for several broad classes of random matrices with dependent entries, including random matrices with subgaussian rows and non-trivial covariance structure, as well as matrices with independent rows, and uniformly bounded entries.
Link Delay Estimation via Expander Graphs by Mohammad H. Firooz, Sumit Roy. The abstract reads:
In network tomography, we seek to infer the status of parameters (such as delay) for links inside a network through end-to-end probing between (external) boundary nodes along chosen routes. In this work, we apply concepts from compressed sensing to establish conditions on the routing matrix under which it is possible to estimate link delay from end-to-end measurements and also provide an upper-bound on the estimation error. Further, we investigate choice of the appropriate set of paths within a given network with defined boundary nodes, so as to minimize the number of probes needed for estimation. Simulation results show that the proposed algorithm will, with high probability, achieve forty percent reduction in overhead required compared to probing between every available pair of boundary nodes.

This paper addresses the problem of inferring sparse causal networks modeled by multivariate auto-regressive (MAR) processes. Conditions are derived under which the Group Lasso (gLasso) procedure consistently estimates sparse network structure. The key condition involves a "false connection score." In particular, we show that consistent recovery is possible even when the number of observations of the network is far less than the number of parameters describing the network, provided that the false connection score is less than one. The false connection score is also demonstrated to be a useful metric of recovery in non-asymptotic regimes. The conditions suggest a modified gLasso procedure which tends to improve the false connection score and reduce the chances of reversing the direction of causal influence. Computational experiments and a real network based electrocorticogram (ECoG) simulation study demonstrate the effectiveness of the approach.

Sunday, June 12, 2011

Coding, Complexity and Sparsity Workshop and SPARS11 detailed program

Spotted on Muthu's blog the CODING, COMPLEXITY AND SPARSITY WORKSHOP. I have added the meeting to the CS meeting list. From the meeting webpage:



Theme:Efficient and effective transmission, storage, and retrieval of information on a large-scale are among the core technical problems in the modern digital revolution. The massive volume of data necessitates the quest for mathematical and algorithmic methods for efficiently describing, summarizing, synthesizing, and, increasingly more critical, deciding when and how to discard data before storing or transmitting it. Such methods have been developed in two areas: coding theory, and sparse approximation (SA) (and its variants called compressive sensing (CS) and streaming algorithms).
Coding theory and computational complexity are both well established fields that enjoy fruitful interactions with one another. On the other hand, while significant progress on the SA/CS problem has been made, much of that progress is concentrated on the feasibility of the problems, including a number of algorithmic innovations that leverage coding theory techniques, but a systematic computational complexity treatment of these problems is sorely lacking. The workshop organizers aim to develop a general computational theory of SA and CS (as well as related areas such as group testing) and its relationship to coding theory. This goal can be achieved only by bringing together researchers from a variety of areas. We will have several tutorial lectures that will be directed to graduate students and postdocs.
Registration: If you are planning to attend the workshop, please register as soon as possible on the registration page. Registration is free and comes with many benefits such as a guest login to access the wireless network on campus. Also, it will help us estimate the number of people attending so that we may plan appropriately for refreshments during the lecture breaks.
Registration deadline: July 15, 2011.
Registered Participants
Lectures: (Please click on the title for more information including an abstract and suggested reading.)
A record of the lectures will be available after the conference.
Confirmed Speakers
Yaniv Erlich
Anna Gilbert
Venkat Guruswami
Brett Hemenway
Piotr Indyk
Dick Lipton
Shachar Lovett
Andrew McGregor
Olgica Milenkovic
Eric Price
Dieter van Melkebeek
Ryan Williams
Virginia Vassilevska Williams
David Woodruff
Instructional Tutorials:
These will be hour-long lectures designed to give students an introduction to the area.
Brett Hemenway, Coding theory
Anna Gilbert, Compressive sensing
Participant support: We have limited support for participants (graduate students and postdocs) to attend. We will be able to cover only a portion of expenses (the standard NSF restrictions apply). To apply, please fill in the following information on the registration page.
Name, University affiliation, Name of graduate advisor/ postdoctoral mentor, a very short description of your research interests, estimated roundtrip travel costs to Ann Arbor, and any travel support available from other sources; e.g., your home institution. In addition, if you are a graduate student, please request your advisor to send a short letter of recommendation to Anna Gilbert .
Schedule and travel:
The local airport is Detroit, airport code DTW. There are taxis and shared ride vans available to Ann Arbor, which is about 25 miles from the airport.
The workshop will begin on Monday, August 1 at 9 am and will end on Thursday, August 4 at 1 pm. Participants are expected to arrive on Sunday, July 31, and leave on Thursday, August 4, in the afternoon or evening. Depending on the arrival/departure schedule of a majority of the participants, we will schedule an afternoon off for a local recreational activity, in the style of a Dagstuhl workshop.
Accommodation:
Blocks of rooms have been reserved at Holiday Inn North and Hampton Inn. (See Lodging)
Useful links:
Airport transportation: Here are some links to shared van rides Ann Arbor Airport Shuttle, Custom Transit, Selectride,Michigan Flyer. Please note there are discounts for people traveling in groups. So participants arriving around the same time can save substantially by coordinating their ground transportation. Also taxis are available from DTW to Ann Arbor for a fixed rate of around $50 - $60.
Local Transportation around Ann Arbor: from the University of Michigan Campus Information Center
Maps: Central Campus (Math Department is in East Hall)



Organizers
Anna Gilbert, Martin Strauss, Atri Rudra,
Hung Ngo, Ely Porat, S. Muthukrishnan
Sponsors
Department of Mathematics, Institute for Mathematics and its
Applications (IMA), NSF, and Michigan Math Journal

In the meantime, the detailed program of SPARS11 is here.

Printfriendly