Dataset Information

Message-passing algorithms for compressed sensing.

ABSTRACT: Compressed sensing aims to undersample certain high-dimensional signals yet accurately reconstruct them by exploiting signal characteristics. Accurate reconstruction is possible when the object to be recovered is sufficiently sparse in a known basis. Currently, the best known sparsity-undersampling tradeoff is achieved when reconstructing by convex optimization, which is expensive in important large-scale applications. Fast iterative thresholding algorithms have been intensively studied as alternatives to convex optimization for large-scale problems. Unfortunately known fast algorithms offer substantially worse sparsity-undersampling tradeoffs than convex optimization. We introduce a simple costless modification to iterative thresholding making the sparsity-undersampling tradeoff of the new algorithms equivalent to that of the corresponding convex optimization procedures. The new iterative-thresholding algorithms are inspired by belief propagation in graphical models. Our empirical measurements of the sparsity-undersampling tradeoff for the new algorithms agree with theoretical calculations. We show that a state evolution formalism correctly derives the true sparsity-undersampling tradeoff. There is a surprising agreement between earlier calculations based on random convex polytopes and this apparently very different theoretical formalism.

SUBMITTER: Donoho DL

PROVIDER: S-EPMC2767368 | biostudies-literature | 2009 Nov

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

Message-passing algorithms for compressed sensing.

Donoho David L DL Maleki Arian A Montanari Andrea A

Proceedings of the National Academy of Sciences of the United States of America 20091026 45

Compressed sensing aims to undersample certain high-dimensional signals yet accurately reconstruct them by exploiting signal characteristics. Accurate reconstruction is possible when the object to be recovered is sufficiently sparse in a known basis. Currently, the best known sparsity-undersampling tradeoff is achieved when reconstructing by convex optimization, which is expensive in important large-scale applications. Fast iterative thresholding algorithms have been intensively studied as alter ...[more]

PMID: 19858495

Similar Datasets

Project description:Cytochrome P450 enzymes aid in the elimination of a preponderance of small molecule drugs, but can generate reactive metabolites that may adversely react with protein and DNA and prompt drug candidate attrition or market withdrawal. Previously developed models help understand how these enzymes modify molecule structure by predicting sites of metabolism or characterizing formation of metabolite-biomolecule adducts. However, the majority of reactive metabolites are formed by multiple metabolic steps, and understanding the progenitor molecule's network-level behavior necessitates an integrative approach that blends multiple site of metabolism and structure inference models. Our previously developed tool, XenoNet 1.0, generates metabolic networks, where nodes are molecules and weighted edges are metabolic transformations. We extend XenoNet with a bidirectional message passing neural network that integrates edge feature information and local network structure using edge-conditioned graph convolutions and jumping knowledge to predict the authenticity of inferred Phase I metabolite structures. Our model significantly outperformed prior work and algorithmic baselines on a data set of 311 networks and 6606 intermediates annotated using a chemically diverse set of 20 736 individual in vitro and in vivo reaction records accounting for 92.3% of all human Phase I metabolism in the Accelrys Metabolite Database. Cross-validated predictions resulted in area under the receiver operating characteristic curves of 88.5% and 87.6% for separating experimentally observed and unobserved metabolites at global and network levels, respectively. Further analysis verified robustness to networks of varying depth and breadth, accurate detection of metabolites, such as d,l-methamphetamine, that are experimentally observed or unobserved in different network contexts, extraction of important metabolic subnetworks, and identification of known bioactivation pathways, such as for nimesulide and terbinafine. By exploiting network structures, our approach accurately suggests unreported metabolites for experimental study and may rationalize modifications for avoiding deleterious pathways antecedent to reactive metabolite formation.

Project description:Neurobiological systems rely on hierarchical and modular architectures to carry out intricate computations using minimal resources. A prerequisite for such systems to operate adequately is the capability to reliably and efficiently transfer information across multiple modules. Here, we study the features enabling a robust transfer of stimulus representations in modular networks of spiking neurons, tuned to operate in a balanced regime. To capitalize on the complex, transient dynamics that such networks exhibit during active processing, we apply reservoir computing principles and probe the systems' computational efficacy with specific tasks. Focusing on the comparison of random feed-forward connectivity and biologically inspired topographic maps, we find that, in a sequential set-up, structured projections between the modules are strictly necessary for information to propagate accurately to deeper modules. Such mappings not only improve computational performance and efficiency, they also reduce response variability, increase robustness against interference effects, and boost memory capacity. We further investigate how information from two separate input streams is integrated and demonstrate that it is more advantageous to perform non-linear computations on the input locally, within a given module, and subsequently transfer the result downstream, rather than transferring intermediate information and performing the computation downstream. Depending on how information is integrated early on in the system, the networks achieve similar task-performance using different strategies, indicating that the dimensionality of the neural responses does not necessarily correlate with nonlinear integration, as predicted by previous studies. These findings highlight a key role of topographic maps in supporting fast, robust, and accurate neural communication over longer distances. Given the prevalence of such structural feature, particularly in the sensory systems, elucidating their functional purpose remains an important challenge toward which this work provides relevant, new insights. At the same time, these results shed new light on important requirements for designing functional hierarchical spiking networks.

Dataset Information

Message-passing algorithms for compressed sensing.

Publications

Message-passing algorithms for compressed sensing.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets