A new bound on the block restricted isometry constant in compressed sensing.
Ontology highlight
ABSTRACT:
SUBMITTER: Gao Y
PROVIDER: S-EPMC5539310 | biostudies-other | 2017
REPOSITORIES: biostudies-other
Similar Datasets
Project description:Compressed sensing (CS) has attracted a great deal of recent interest as an approach for spectrum analysis of nonuniformly sampled NMR data. Although theoretical justification for the method is abundant, it suffers from several weaknesses, among them poor convergence of some algorithms, and it remains an open question whether NMR spectra satisfy the sparsity requirements of CS theorems. The versions of CS used in NMR involve minimizing the l1 norm of the spectrum. They bear similarity to maximum entropy (MaxEnt) reconstruction, but critical comparison of the methods can be difficult. Here we describe a formalism that places CS and MaxEnt reconstruction on equal footing, enabling critical comparison of the two methods. We also describe a new algorithm for CS that restricts the computation of the l1 norm to the real channel for complex spectra and ensures causality. Preliminary 1D results demonstrate that this approach ameliorates some artifacts that can occur when using the l1 norm of the complex spectrum.
| S-EPMC5776145 | biostudies-literature
Project description:In super-resolution microscopy methods based on single-molecule switching, the rate of accumulating single-molecule activation events often limits the time resolution. Here we developed a sparse-signal recovery technique using compressed sensing to analyze images with highly overlapping fluorescent spots. This method allows an activated fluorophore density an order of magnitude higher than what conventional single-molecule fitting methods can handle. Using this method, we demonstrated imaging microtubule dynamics in living cells with a time resolution of 3 s.
| S-EPMC3477591 | biostudies-literature
Project description: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.
| S-EPMC2767368 | biostudies-literature
Project description:The AI community has been paying attention to submodular functions due to their various applications (e.g., target search and 3D mapping). Learning submodular functions is a challenge since the number of a function's outcomes of N sets is 2 N . The state-of-the-art approach is based on compressed sensing techniques, which are to learn submodular functions in the Fourier domain and then recover the submodular functions in the spatial domain. However, the number of Fourier bases is relevant to the number of sets' sensing overlapping. To overcome this issue, this research proposed a submodular deep compressed sensing (SDCS) approach to learning submodular functions. The algorithm consists of learning autoencoder networks and Fourier coefficients. The learned networks can be applied to predict 2 N values of submodular functions. Experiments conducted with this approach demonstrate that the algorithm is more efficient than the benchmark approach.
| S-EPMC7249116 | biostudies-literature
Project description:The accurate detection of targets is a significant problem in multiple-input multiple-output (MIMO) radar. Recent advances of Compressive Sensing offer a means of efficiently accomplishing this task. The sparsity constraints needed to apply the techniques of Compressive Sensing to problems in radar systems have led to discretizations of the target scene in various domains, such as azimuth, time delay, and Doppler. Building upon recent work, we investigate the feasibility of on-grid Compressive Sensing-based MIMO radar via a threefold azimuth-delay-Doppler discretization for target detection and parameter estimation. We utilize a colocated random sensor array and transmit distinct linear chirps to a small scene with few, slowly moving targets. Relying upon standard far-field and narrowband assumptions, we analyze the efficacy of various recovery algorithms in determining the parameters of the scene through numerical simulations, with particular focus on the ? 1-squared Nonnegative Regularization method.
| S-EPMC4870333 | biostudies-literature
Project description:Recent methods for spatial imaging of tissue samples can identify up to ~100 individual proteins1-3 or RNAs4-10 at single-cell resolution. However, the number of proteins or genes that can be studied in these approaches is limited by long imaging times. Here we introduce Composite In Situ Imaging (CISI), a method that leverages structure in gene expression across both cells and tissues to limit the number of imaging cycles needed to obtain spatially resolved gene expression maps. CISI defines gene modules that can be detected using composite measurements from imaging probes for subsets of genes. The data are then decompressed to recover expression values for individual genes. CISI further reduces imaging time by not relying on spot-level resolution, enabling lower magnification acquisition, and is overall about 500-fold more efficient than current methods. Applying CISI to 12 mouse brain sections, we accurately recovered the spatial abundance of 37 individual genes from 11 composite measurements covering 180 mm2 and 476,276 cells.
| S-EPMC8355028 | biostudies-literature
Project description:PurposeTo develop a method that combines parallel imaging and compressed sensing to enable faster and/or higher spatial resolution magnetic resonance (MR) imaging and show its feasibility in a pediatric clinical setting.Materials and methodsInstitutional review board approval was obtained for this HIPAA-compliant study, and informed consent or assent was given by subjects. A pseudorandom k-space undersampling pattern was incorporated into a three-dimensional (3D) gradient-echo sequence; aliasing then has an incoherent noiselike pattern rather than the usual coherent fold-over wrapping pattern. This k-space-sampling pattern was combined with a compressed sensing nonlinear reconstruction method that exploits the assumption of sparsity of medical images to permit reconstruction from undersampled k-space data and remove the noiselike aliasing. Thirty-four patients (15 female and 19 male patients; mean age, 8.1 years; range, 0-17 years) referred for cardiovascular, abdominal, and knee MR imaging were scanned with this 3D gradient-echo sequence at high acceleration factors. Obtained k-space data were reconstructed with both a traditional parallel imaging algorithm and the nonlinear method. Both sets of images were rated for image quality, radiologist preference, and delineation of specific structures by two radiologists. Wilcoxon and symmetry tests were performed to test the hypothesis that there was no significant difference in ratings for image quality, preference, and delineation of specific structures.ResultsCompressed sensing images were preferred more often, had significantly higher image quality ratings, and greater delineation of anatomic structures (P < .001) than did images obtained with the traditional parallel reconstruction method.ConclusionA combination of parallel imaging and compressed sensing is feasible in a clinical setting and may provide higher resolution and/or faster imaging, addressing the challenge of delineating anatomic structures in pediatric MR imaging.
| S-EPMC2909438 | biostudies-literature
Project description:BACKGROUND:The aim of a genome-wide association study (GWAS) is to isolate DNA markers for variants affecting phenotypes of interest. This is constrained by the fact that the number of markers often far exceeds the number of samples. Compressed sensing (CS) is a body of theory regarding signal recovery when the number of predictor variables (i.e., genotyped markers) exceeds the sample size. Its applicability to GWAS has not been investigated. RESULTS:Using CS theory, we show that all markers with nonzero coefficients can be identified (selected) using an efficient algorithm, provided that they are sufficiently few in number (sparse) relative to sample size. For heritability equal to one (h (2) = 1), there is a sharp phase transition from poor performance to complete selection as the sample size is increased. For heritability below one, complete selection still occurs, but the transition is smoothed. We find for h (2) ? 0.5 that a sample size of approximately thirty times the number of markers with nonzero coefficients is sufficient for full selection. This boundary is only weakly dependent on the number of genotyped markers. CONCLUSION:Practical measures of signal recovery are robust to linkage disequilibrium between a true causal variant and markers residing in the same genomic region.?Given a limited sample size, it is possible to discover a phase transition by increasing the penalization; in this case a subset of the support may be recovered. Applying this approach to the GWAS analysis of height, we show that 70-100% of the selected markers are strongly correlated with height-associated markers identified by the GIANT Consortium.
| S-EPMC4078394 | biostudies-literature
Project description:BACKGROUND:One of the fundamental problems of modern genomics is to extract the genetic architecture of a complex trait from a data set of individual genotypes and trait values. Establishing this important connection between genotype and phenotype is complicated by the large number of candidate genes, the potentially large number of causal loci, and the likely presence of some nonlinear interactions between different genes. Compressed Sensing methods obtain solutions to under-constrained systems of linear equations. These methods can be applied to the problem of determining the best model relating genotype to phenotype, and generally deliver better performance than simply regressing the phenotype against each genetic variant, one at a time. We introduce a Compressed Sensing method that can reconstruct nonlinear genetic models (i.e., including epistasis, or gene-gene interactions) from phenotype-genotype (GWAS) data. Our method uses L1-penalized regression applied to nonlinear functions of the sensing matrix. RESULTS:The computational and data resource requirements for our method are similar to those necessary for reconstruction of linear genetic models (or identification of gene-trait associations), assuming a condition of generalized sparsity, which limits the total number of gene-gene interactions. An example of a sparse nonlinear model is one in which a typical locus interacts with several or even many others, but only a small subset of all possible interactions exist. It seems plausible that most genetic architectures fall in this category. We give theoretical arguments suggesting that the method is nearly optimal in performance, and demonstrate its effectiveness on broad classes of nonlinear genetic models using simulated human genomes and the small amount of currently available real data. A phase transition (i.e., dramatic and qualitative change) in the behavior of the algorithm indicates when sufficient data is available for its successful application. CONCLUSION:Our results indicate that predictive models for many complex traits, including a variety of human disease susceptibilities (e.g., with additive heritability h (2)?0.5), can be extracted from data sets comprised of n ??100s individuals, where s is the number of distinct causal variants influencing the trait. For example, given a trait controlled by ?10 k loci, roughly a million individuals would be sufficient for application of the method.
| S-EPMC4570224 | biostudies-literature
Project description:There has been growing interest in applying compressed sensing (CS) theory and practice to reconstruct 3D volumes at the nanoscale from electron tomography datasets of inorganic materials, based on known sparsity in the structure of interest. Here we explore the application of CS for visualizing the 3D structure of biological specimens from tomographic tilt series acquired in the scanning transmission electron microscope (STEM). CS-ET reconstructions match or outperform commonly used alternative methods in full and undersampled tomogram recovery, but with less significant performance gains than observed for the imaging of inorganic materials. We propose that this disparity stems from the increased structural complexity of biological systems, as supported by theoretical CS sampling considerations and numerical results in simulated phantom datasets. A detailed analysis of the efficacy of CS-ET for undersampled recovery is therefore complicated by the structure of the object being imaged. The numerical nonlinear decoding process of CS shares strong connections with popular regularized least-squares methods, and the use of such numerical recovery techniques for mitigating artifacts and denoising in reconstructions of fully sampled datasets remains advantageous. This article provides a link to the software that has been developed for CS-ET reconstruction of electron tomographic data sets.
| S-EPMC4904377 | biostudies-literature