Hi Igor,
there is a recent paper in Nature that might be of interest to you:
http://www.nature.com/nature/journal/v470/n7332/full/nature09750.html
several terabytes of data were processed using fairly standard crystallographic software, but we are investigating better ways. The connection with compressive sensing is made here:
http://arxiv.org/abs/1011.3072
The model was very simple and needs work, I include the code used for the figures of that paper, in case you are interested, (it takes too much paperwork to publish it myself).
Cheers,
Stefano
X-ray crystallography provides the vast majority of macromolecular structures, but the success of the method relies on growing crystals of sufficient size. In conventional measurements, the necessary increase in X-ray dose to record data from crystals that are too small leads to extensive damage before a diffraction signal can be recorded1, 2, 3. It is particularly challenging to obtain large, well-diffracting crystals of membrane proteins, for which fewer than 300 unique structures have been determined despite their importance in all living cells. Here we present a method for structure determination where single-crystal X-ray diffraction ‘snapshots’ are collected from a fully hydrated stream of nanocrystals using femtosecond pulses from a hard-X-ray free-electron laser, the Linac Coherent Light Source4. We prove this concept with nanocrystals of photosystem I, one of the largest membrane protein complexes5. More than 3,000,000 diffraction patterns were collected in this study, and a three-dimensional data set was assembled from individual photosystem I nanocrystals (~200 nm to 2 μm in size). We mitigate the problem of radiation damage in crystallography by using pulses briefer than the timescale of most damage processes6. This offers a new approach to structure determination of macromolecules that do not yield crystals of sufficient size for studies using conventional radiation sources or are particularly sensitive to radiation damage.
Ultrafast nanocrystallography has the potential to revolutionize biology by enabling structural elucidation of proteins for which it is possible to grow crystals with 10 or fewer unit cells on the side. The success of nanocrystallography depends on robust orientation-determination procedures that allow us to average diffraction data from multiple nanocrystals to produce a three dimensional (3D) diffraction data volume with a high signal-to-noise ratio. Such a 3D diffraction volume can then be phased using standard crystallographic techniques. "Indexing" algorithms used in crystallography enable orientation determination of diffraction data from a single crystal when a relatively large number of reflections are recorded. Here we show that it is possible to obtain the exact lattice geometry from a smaller number of measurements than standard approaches using a basis pursuit solver.
This is a very interesting paper. An eloquent introduction states:The idea that many important classes of signals can be well-represented by linear combinations of a small set of atoms selected from a given dictionary has had dramatic impact on the theory and practice of signal processing. For practical problems in which an appropriate sparsifying dictionary is not known ahead of time, a very popular and successful heuristic is to search for a dictionary that minimizes an appropriate sparsity surrogate over a given set of sample data. While this idea is appealing, the behavior of these algorithms is largely a mystery; although there is a body of empirical evidence suggesting they do learn very effective representations, there is little theory to guarantee when they will behave correctly, or when the learned dictionary can be expected to generalize. In this paper, we take a step towards such a theory. We show that under mild hypotheses, the dictionary learning problem is locally well-posed: the desired solution is indeed a local minimum of the $\ell^1$ norm. Namely, if $\mb A \in \Re^{m \times n}$ is an incoherent (and possibly overcomplete) dictionary, and the coefficients $\mb X \in \Re^{n \times p}$ follow a random sparse model, then with high probability $(\mb A,\mb X)$ is a local minimum of the $\ell^1$ norm over the manifold of factorizations $(\mb A',\mb X')$ satisfying $\mb A' \mb X' = \mb Y$, provided the number of samples $p = \Omega(n^3 k)$. For overcomplete $\mb A$, this is the first result showing that the dictionary learning problem is locally solvable. Our analysis draws on tools developed for the problem of completing a low-rank matrix from a small subset of its entries, which allow us to overcome a number of technical obstacles; in particular, the absence of the restricted isometry property.
This idea has several appeals: Given the recent proliferation of new and exotic types of data (images, videos, web and bioinformatic data, ect.), it may not be possible to invest the intellectual e ort required to develop optimal representations for each new class of signal we encounter. At the same time, data are becoming increasingly high-dimensional, a fact which stretches the limitations of our human intuition, potentially limiting our ability to develop e ective data representations. It may be possible for an automatic procedure to discover useful structure in the data that is not readily apparent to us.
The richness of natural images makes the quest for optimal representations in image processing and computer vision challenging. This fact has not prevented the design of candidates, convenient for rendering smooth regions, contours and textures at the same time, with compromises between efficiency and complexity. The most recent ones, proposed in the past decade, share an hybrid heritage highlighting the multiscale and oriented nature of edges and patterns in images. This paper endeavors a panorama of the aforementioned literature on decompositions in multiscale, multi-orientation bases or dictionaries. They typically exhibit redundancy to improve both the sparsity of the representation, and sometimes its invariance to various geometric deformations. Oriented multiscale dictionaries extend traditional wavelet processing and may offer rotation invariance. Highly redundant dictionaries require specific algorithms to simplify the search for an efficient (sparse) representation. We also discuss the extension of multiscale geometric decompositions to non-Euclidean domains such as the sphere $S^2$ and arbitrary meshed surfaces in $\Rbb^3$. The apt and patented etymology of panorama suggests an overview based on a choice of overlapping "pictures", i.e., selected from a broad set of computationally efficient mathematical tools. We hope this work help enlighten a substantial fraction of the present exciting research in image understanding, targeted to better capture data diversity.
We present an abstract framework that allows for Compressed Sensing in infinite dimensions. We show that the combination of a the recently developed Generalized Sampling Theorem (that is a generalization of the classical Shannon Sampling Theorem and allows for reconstructions in arbitrary bases) and infinite-dimensional compressed sensing not only allows for reconstructions in arbitrary bases, but also allows for substantial under sampling. As a corollary of our framework we solve an open problem in finite-dimensional compressed sensing, namely, we demonstrate that the results shown by Candès, Romberg and Tao in [10] on the discrete Fourier transform extends to arbitrary unitary matrices.
Remark 2.3. The well informed reader may object and suggest that if we have a signal g that is sparse in the Haar basis, why are we not “measuring” g with noiselets [14] (e.g. obtaining inner products hφj , gi for j ∈ N where the φjs are noiselets ) which would give us a finite-dimensional recovery problem a la (2.4). In that case n · υ2(U) = 1 in Theorem 2.2 (perfect incoherence) and thus we would have a very well suited recovery problem. The only problem is that the luxury to choose the measurements are very rare in applications. In particular, in the example that we just considered (and which replicates an MRI situation) we are given f = Fg, the Fourier transform of g. And thus the measurements are hϕj , gi for j ∈ Z and ϕj(x) = e−2πijǫx. This is due to the physics behind the MRI equipment and can therefore not be altered (in particular, measurements with noiselets are impossible). Thus, we must have a model for which the sampling vectors, say {ϕj}j∈N, are fixed!
"...About if I've tried to contact with the authors, but only one of them answered my e-mails and telling me that he can't help, because the code of that example can't be distributed,..."
Carron I. Nuit Blanche Blog [Internet]. Igor Carron, 2003 Nov - [cited 2008 May 16]. Available from: http://nuit-blanche.blogspot.com/.
Gemmeke J. Nuit Blanche Blog [Internet]. Igor Carron, 2003 Nov - [cited 2007 November 19]. Available from: http://nuit-blanche.blogspot.com/.
Compressive Sensing: The Big Picture [Internet]. Igor Carron, 2009. Available from: http://sites.google.com/site/igorcarron2/cs
Jan 31, 2011, Postdoc, Technion We are seeking a highly motivated, talented, and fun post-doctorate fellow, for exciting research in the area of compressed sensing applied to analog signals with applications to low-rate analog-to-digital conversion, ultrasound imaging, radar systems, cognitive radio and more.Finally, two series of talks:
The research will involve tight interaction between engineering (signal processing and hardware
design) and applied mathematics and statistics. This project provides a unique opportunity to conduct research on topics that are in the frontier of signal processing and sampling theory, while at the same time have direct impact on industrial applications. Our labs are equipped with state-of-the art equipment from several companies interested in advanced sampling techniques for next generation radar/ultrasound/wireless systems and more. See http://webee.technion.ac.il/Sites/People/YoninaEldar/Info/hardware.html for a description of some current projects.
Potential candidates should have:
* An established research record with solid publications and the ability to work independently;
* Strong background in applied mathematics (relevant specialties are: sampling theory, optimization, signal processing, harmonic analysis);
* Knowledge of RF theory and design is a big advantage (but not necessary);
* A true desire to collaborate and be part of a team which will include both mathematicians and
analog design experts.
This project will offer the opportunity to collaborate closely with renowned experts in a stimulating intellectual environment, including the latest equipment in RF, radar, and other areas.
The working conditions at the Technion are excellent. The Department of Electrical Engineering of the Technion is ranked among the "top 10" Electrical Engineering and Computer Science departments in the world. The department is the major source of engineers who lead the development of advanced Israeli technology in the fields of electronics, computers and communications. A recent international review ranked the labs, the projects, and the student quality as "second to none". The Technion is located in Haifa, a beautiful vibrant port-city on the Mediterranean.
Details:
Starting time: Spring/Summer 2011 and onwards.
Duration: An initial contract of 1 year duration will be offered to the successful candidate, with a
possibility of extension.
Interested candidates are invited to send their CV with names of 2 references to Prof. Yonina Eldar at yonina@ee.technion.ac.il
http://webee.technion.ac.il/Sites/People/YoninaEldar/
Colorado State University’s Information Science and Technology Center (ISTeC) presents two lectures by Georgios Giannakis, Ph.D., ADC Endowed Chair Professor, Director, Digital Technology Center, Department of Electrical and Computer Engineering, University of Minnesota.
Both lectures are open to the public.
The first event is a ISTeC Distinguished Lecture in conjunction with the Electrical and Computer Engineering Department and Computer Science Department Seminar Series.
Wireless Cognitive Communications
* Monday, Jan. 31
* Reception: 10:30 a.m.
* Lecture: 11-noon
* Location: Lory Student Center, Room 205
Abstract
Exciting research and development efforts provide ample testament to the fact that wireless cognitive radio (CR) technology holds great promise to address fruitfully the perceived dilemma of bandwidth under-utilization versus spectrum scarcity, which has rendered the current fixed-access communication networks inefficient.
Accordingly, the need arises for intelligent radios equipped with critical cognition infrastructure to sense, learn, and adapt to their operational radio frequency (RF) ambiance. This talk outlines such an infrastructure for comprehensive situation awareness using the novel notion of RF cartography, which amounts to constructing maps capturing the distribution of power across space, time, and frequency; as well as the propagation medium per frequency from each node to any point in space and time.
Mimicking the way we rely on AAA or GPS-generated maps to navigate our cars, the vision is to utilize these maps for:
1. Identification of opportunistically available bands
2. Localization, and tracking of other radios
3. Interference control, resource allocation, and information routing
We consider the problem of identifying a pattern of faults from a set of noisy linear measurements. Unfortunately, maximum a posteriori probability estimation of the fault pattern is computationally intractable. To solve the fault identification problem, we propose a non-parametric belief propagation approach. We show empirically that our belief propagation solver is more accurate than recent state-of-the-art algorithms including interior point methods and semidefinite programming. Our superior performance is explained by the fact that we take into account both the binary nature of the individual faults and the sparsity of the fault pattern arising from their rarity.
Recovery of functions of many variables from sample values usually suffers the curse of dimensionality: The number of required samples scales exponentially with the spatial dimension. In order to avoid this severe bottleneck, one needs to impose further structural properties of the function to be recovered apart from smoothness. Here, we build on ideas from compressive sensing and introduce a function model that involves “sparsity with respect to dimensions” in the Fourier domain. Using recent estimates on the restricted isometry constants of measurement matrices associated to randomly sampled trigonometric systems, we show that the number of required samples scales only logarithmically in the spatial dimension provided the function to be recovered follows the newly introduced highdimensional function model.
A Nonlinear Approach to Dimension Reduction by Lee-Ad Gottlieb, Robert Krauthgamer. The abstract reads:Sparse signal priors help in a variety of modern signal processing tasks. In many cases, a sparse signal needs to be recovered from an underdetermined system of equations. For instance, sparse approximation of a signal with an overcomplete dictionary or reconstruction of a sparse signal from a small number of linear measurements. The reconstruction problem typically requires solving an `1 norm minimization problem. In this paper we present homotopy based algorithms to update the solution of some `1 problems when the system is updated by adding new rows or columns to the underlying system matrix. We also discuss a case where these ideas can be extended to accommodate for more general changes in the system matrix.
The ℓ2 flattening lemma of Johnson and Lindenstrauss [JL84] is a powerful tool for dimension reduction. It has been conjectured that the target dimension bounds can be refined and bounded in terms of the intrinsic dimensionality of the data set (for example, the doubling dimension). One such problem was proposed by Lang and Plaut [LP01] (see also [GKL03, Mat02, ABN08, CGT10]), and is still open. We prove another result in this line of work: The snowflake metric d1/2 of a doubling set S ⊂ ℓ2 can be embedded with arbitrarily low distortion into ℓD2, for dimension D that depends solely on the doubling constant of the metric. In fact, the target dimension is polylogarithmic in the doubling constant. Our techniques are robust and
extend to the more difficult spaces ℓ1 and ℓ∞, although the dimension bounds here are quantitatively inferior than those for ℓ2.
The inverse problem of finding sparse initial data from the solutions to the heat equation is considered. The initial data is assumed to be a sum of an unknown but nite number of Dirac delta functions at unknown locations. Point-wise values of the heat solution at only a few locations are used in an L1 constrained optimization to find such sparse initial data. A concept of domain of effective sensing is introduced to speed up the already fast Bregman iterative algorithm for L1 optimization. Furthermore, an algorithm which successively adds new measurements at intelligent locations is introduced. By comparing the solutions of the inverse problem that are obtained from different number of measurements, the algorithm decides where to add new measurements in order to improve the reconstruction of the sparse initial data.
It is nice to see this fact acknowledged.In compressed sensing [7], we can solve an L0 problems by solving its L1 relaxation when the associated matrix has the restricted isometry property (RIP) [6]. The heat operator does not satisfy RIP, but we can adopt the idea of substituting L0 with L1 for sparse optimization. We will show numerical results which indicate the effectiveness of this strategy. Our approach to this problem is to solve a L1 minimization problem with constraints. We apply the Bregman iterative method [9, 13] to solve the constrained problem as a sequence of unconstrained subproblems. To solve these subproblems, we use the greedy coordinate descent method developed in [11] for solving the L1 unconstrained problem, which was shown to be very efficient for sparse recovery.
Embedded computing and sensing are entrenched in many facets of daily life. Embedded devices must be able to collect large amounts of data from multiple sources, and then present the user with an “executive summary” of the observations. A user can then use this distilled information to quickly plan a course of action. It is therefore imperative that new methods are explored for distilling data to a form that is suitable for a user. Furthermore, the prevalence of wireless communications demands that relevant information be preextracted from high-dimension data in order to reduce bandwidth, memory, and energy requirements. Applications of interest to the EI such as structural health monitoring (SHM) and treaty verification typically require the collection of data from large arrays of wireless sensor nodes at high data rates. Data from different sensors must be combined in order to draw inferences about the state of the system under observation. The sensor nodes used to collect these data typically have severe data storage and energy constraints. Wireless transmission of data must be executed in a thoughtful manner and only the most relevant data should be committed to memory. Recently, compressed sensing has presented itself as a candidate solution for directly collecting relevant information from sparse, highdimensional measurements. The main idea behind compressed sensing is that, by directly collecting a relatively small number of coefficients, it is possible to reconstruct the original measurement. The coefficients are derived from linear combinations of measurements. Conveniently, most signals found in nature are indeed sparse with the notable exception of noise. The findings of the compressed sensing community hold great potential for changing the way data are collected. EI and ISR researchers (David Mascarenas, Chuck Farrar, Don Hush, James Thieler) has begun exploring the possibility of incorporating compressed sensing principles into SHM and treaty verification wireless sensor nodes. Advantages offered by compressed sensing include lower energy use for data collection and transmission, as well as reduced memory requirements. Compressed coefficients also have the interesting property that they are democratic, in the sense that no individual coefficient has any more information than any other. In this way they exhibit some robustness against data corruption. It is also worth noting that compressed sensing versions of conventional statistical signal processing techniques have been adopted by EI based on the use of smashed filters. The extension of statistical signal processing to the compressed domain helps facilitate the transition of the SHM strategies to take advantage of compressed sensing techniques. Currently, a digital version of the compressed sensor onboard a microcontroller is developed. (shown in Figure). This compressed sensor node is being tested for a SHM application requiring acceleration measurements, as well as a CO2 climate treaty verification application. The prototype compressed sensor is capable of collecting compressed coefficients from measurements and sending them to an off-board processor for reconstruction. In addition, the smashed filter has also been implemented onboard the embedded compressed sensor node. Preliminary results have shown that the smashed filter successfully distinguishes between the damaged and undamaged states using only 1/32 the number of measurements used in the conventional matched filter. EI plans to extend the compressive sensing to the mobile-host wireless sensing network architectures that has been studied in the past, as compressed sensing holds great promise for distilling data collected from wireless sensor networks.
All I know is that Nuit Blanche ain't:Math blogs are a great way for professors, scientists, and researchers to convey the purpose of their work to a broader audience. Some bloggers offer an introduction to mathematical concepts and current research, while others post updates on their research and interests. The following 50 blogs are the cream of the crop: entertaining and informative posts that have something to offer for math geeks of all stripes.
In most compressive sensing problems l1 norm is used during the signal reconstruction process. In this article the use of entropy functional is proposed to approximate the l1 norm. A modified version of the entropy functional is continuous, differentiable and convex. Therefore, it is possible to construct globally convergent iterative algorithms using Bregman's row action D-projection method for compressive sensing applications. Simulation examples are presented.I wonder when a solver will be available.
We propose a factor-graph-based approach to joint channel-estimation-and-decoding (JCED) of bit- interleaved coded orthogonal frequency division multiplexing (BICM-OFDM). In contrast to existing designs, ours is capable of exploiting not only sparsity in sampled channel taps but also clustering among the large taps, behaviors which are known to manifest at larger communication bandwidths. In order to exploit these channel-tap structures, we adopt a two-state Gaussian mixture prior in conjunction with a Markov model on the hidden state. For loopy belief propagation, we exploit a "generalized approximate message passing" (GAMP) algorithm recently developed in the context of compressed sensing, and show that it can be successfully coupled with soft-input soft-output decoding, as well as hidden Markov inference, through the standard sum-product framework. For N subcarriers and M bits per subcarrier (and any channel length L \lt N), the resulting JCED-GAMP scheme has a computational complexity of only O(N log2 N+N 2^M). Numerical experiments show that our scheme yields BER performance within 1 dB of the known-channel bound and 4 dB better than decoupled channel-estimation-and-decoding via LASSO.
Detection of Patterns in Networks
ECE Seminar Series
Friday, February 4, 2011
12:00 - 2:00 PM
ENS 637
Dr. Randy C. Paffenroth
Numerica Corporation
Abstract
Discuss the development and application of a mathematical and computational framework for detecting and classifying weak, distributed patterns in sensor networks. The work being done at Numerica demonstrates the effectiveness of space-time inference on graphs, robust matrix completion and second order analysis in the detection and classification of distributed patterns that are not discernible at the level of individual nodes. Our focus is on cyber security scenarios where computer nodes (such as terminals, routers and servers) are sensors that provide measurements of packet rates, user activity, central processing unit usage, etc. When viewed independently, they cannot provide a definitive determination of the underlying pattern, but when fused with data from across the network – both spatially and temporally – the relevant patterns emerge. The clear underlying suggestion is that only detectors and classifiers that use a rigorous mathematical analysis of temporal measurements at many spatially distributed points in the network can identify network attacks. This research builds upon work in compressed sensing and robust matrix completion and is an excellent example of industry-academic collaboration.
GE/IE 590 Seminar-Large-Scale Optimization with Applications in Compressed Sensing
Speaker Professor Fatma Kilinc-Karzan
Date Feb 3, 2011
Time 4:00 pm
Location 101 Transportation Building
Cost Free
Sponsor ISE
Contact Holly Tipsword
E-Mail tippy6@illinois.edu
Phone 217-333-2730
Views 4
In this talk, we will cover some of the recent developments in large-scale optimization motivated by the compressed sensing paradigm. Sparsity plays a key role in dealing with high-dimensional data sets. Exploiting this fact, compressed sensing suggests a new paradigm by directly acquiring and storing only a few linear measurements (possibly corrupted with noise) of high-dimensional signals, and then using efficient -recovery procedures for reconstruction. Successful applications of this theory range from MRI image processing to statistics and machine learning. This talk will have two main parts. In the first part, after presenting the necessary background from compressed sensing, we will show that prior results can be generalized to utilize a priori information given in the form of sign restrictions on the signal. We will investigate the underlying conditions allowing successful -recovery of sparse signals and show that these conditions although difficult to evaluate lead to sufficient conditions that can be efficiently verified via linear or semidefinite programming. We will analyze the properties of these conditions, and describe their limits of performance. In the second part, we will develop efficient first-order methods with both deterministic and stochastic oracles for solving large-scale well-structured convex optimization problems. As an application of this theory, we will show how large-scale problems originating from compressed sensing fall into this framework. We will conclude with numerical results demonstrating the effectiveness of our algorithms.
