Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Sparsity”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 55 records · Page 3

Exploiting sparsity for the min k -partition problem

The minimum k-partition problem is a challenging combinatorial problem with a diverse set of applications ranging from telecommunications to sports scheduling. It generalizes the max-cut problem and has been extensively studied since the late sixties. Strong integer formulations proposed in the literature suffer from a large number of constraints and variables. Here, we introduce two more compact integer linear and semidefinite reformulations that exploit the sparsity of the underlying graph and develop theoretical results leveraging the power of chordal decomposition. Numerical experiments show that the new formulations improve upon state-of-the-art.

97 MATHEMATICS AND COMPUTING↗

Sparsity Facilitates Chemical-Reaction Selection for Engine Simulations

Analysis of large-scale, realistic models incorporating detailed chemistry can be challenging because each simulation is computationally expensive, and a complete analysis may require many simulations. This paper addresses one such problem of this type, chemical-reaction selection in engine simulations. In this computationally challenging case, it is demonstrated how the important concept of sparsity can facilitate chemical-reaction selection, which is the process of finding the most important chemical reactions for modeling a chemical process. It is difficult to perform accurate reaction selection for engine simulations using realistic models of the chemistry, as each simulation takes processor weeks to complete. We developed a procedure to efficiently accomplish this selection process with a relatively small number of simulations using a form of global sensitivity analysis based on sparse regression. The chemical-reaction selection leads to an analysis of the ignition chemistry as it evolves within the compression-ignition engine simulations and allows for the spatial development of the selected chemical reactions to be studied in detail.

Magnotti, Gina M.↗

Atomic orbital-based SOS-MP2 with tensor hypercontraction. I. GPU-based tensor construction and exploiting sparsity

We present a tensor hypercontracted (THC) scaled opposite spin second order Møller-Plesset perturbation theory (SOS-MP2) method. By using THC, we reduce the formal scaling of SOS-MP2 with respect to molecular size from quartic to cubic. We achieve further efficiency by exploiting sparsity in the atomic orbitals and using graphical processing units (GPUs) to accelerate integral construction and matrix multiplication. The practical scaling of GPU-accelerated atomic orbital-based THC-SOS-MP2 calculations is found to be N{sup 2.6} for reference data sets of water clusters and alanine polypeptides containing up to 1600 basis functions. The errors in correlation energy with respect to density-fitting-SOS-MP2 are less than 0.5 kcal/mol for all systems tested (up to 162 atoms).

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

SPECTROSCOPY FROM PHOTOMETRY USING SPARSITY: THE SDSS CASE STUDY

We explore whether medium-resolution stellar spectra can be reconstructed from photometric observations, taking advantage of the highly compressible nature of the spectra. We formulate the spectral reconstruction as a least-squares problem with a sparsity constraint. In our test case using data from the Sloan Digital Sky Survey, only three broadband filters are used as input. We demonstrate that reconstruction using three principal components is feasible with these filters, leading to median differences with respect to the original spectrum smaller than 5%. We analyze the effect of uncertainties in the observed magnitudes and find that the available high photometric precision induces very small errors in the reconstruction. This process may facilitate the extraction of purely spectroscopic quantities, such as the overall metallicity, for hundreds of millions of stars for which only photometric information is available, using standard analysis techniques applied to the reconstructed spectra.

79 ASTRONOMY AND ASTROPHYSICS↗

Improving Weak Lensing Mass Map Reconstructions using Gaussian and Sparsity Priors: Application to DES SV

Mapping the underlying density field, including non-visible dark matter, using weak gravitational lensing measurements is now a standard tool in cosmology. Due to its importance to the science results of current and upcoming surveys, the quality of the convergence reconstruction methods should be well understood. We compare three methods: Kaiser–Squires (KS), Wiener filter, and Glimpse. Kaiser–Squires is a direct inversion, not accounting for survey masks or noise. The Wiener filter is well-motivated for Gaussian density fields in a Bayesian framework. Glimpse uses sparsity, aiming to reconstruct non-linearities in the density field. We compare these methods with several tests using public Dark Energy Survey (DES) Science Verification (SV) data and realistic DES simulations. The Wiener filter and Glimpse offer substantial improvements over smoothed Kaiser–Squires with a range of metrics. Both the Wiener filter and Glimpse convergence reconstructions show a 12 per cent improvement in Pearson correlation with the underlying truth from simulations. To compare the mapping methods’ abilities to find mass peaks, we measure the difference between peak counts from simulated ΛCDM shear catalogues and catalogues with no mass fluctuations (a standard data vector when inferring cosmology from peak statistics); the maximum signal-to-noise of these peak statistics is increased by a factor of 3.5 for the Wiener filter and 9 for Glimpse. With simulations, we measure the reconstruction of the harmonic phases; the phase residuals’ concentration is improved 17 per cent by Glimpse and 18 per cent by the Wiener filter. The correlationbetween reconstructions from data and foreground redMaPPer clusters is increased 18 per cent by the Wiener filter and 32 per cent by Glimpse.

79 ASTRONOMY AND ASTROPHYSICS↗

Adapting In Situ Accelerators for Sparsity With Granular Matrix Reordering

Neural network (NN) inference is an essential part of modern systems and is found at the heart of numerous applications ranging from image recognition to natural language processing. In situ NN accelerators can efficiently perform NN inference using resistive crossbars, which makes them a promising solution to the data movement challenges faced by conventional architectures. Although such accelerators demonstrate significant potential for dense NNs, they often do not benefit from sparse NNs, which contain relatively few non-zero weights. Processing sparse NNs on in situ accelerators results in wasted energy to charge the entire crossbar where most elements are zeros. To address this limitation, this paper proposes Granular Matrix Reordering (GMR): a preprocessing technique that enables an energy-efficient computation of sparse NNs on in situ accelerators. GMR reorders the rows and columns of sparse weight matrices to maximize the crossbars' utilization and minimize the total number of crossbars needed to be charged. The reordering process does not rely on sparsity patterns and incurs no accuracy loss. Finally, GMR achieves an average of 28% and up to 34% reduction in energy consumption over seven pruned NNs across four different pruning methods and network architectures.

97 MATHEMATICS AND COMPUTING↗

Sparsity-based acoustic inversion in cross-sectional multiscale optoacoustic imaging

Purpose: With recent advancement in hardware of optoacoustic imaging systems, highly detailed cross-sectional images may be acquired at a single laser shot, thus eliminating motion artifacts. Nonetheless, other sources of artifacts remain due to signal distortion or out-of-plane signals. The purpose of image reconstruction algorithms is to obtain the most accurate images from noisy, distorted projection data. Methods: In this paper, the authors use the model-based approach for acoustic inversion, combined with a sparsity-based inversion procedure. Specifically, a cost function is used that includes the L1 norm of the image in sparse representation and a total variation (TV) term. The optimization problem is solved by a numerically efficient implementation of a nonlinear gradient descent algorithm. TV–L1 model-based inversion is tested in the cross section geometry for numerically generated data as well as for in vivo experimental data from an adult mouse. Results: In all cases, model-based TV–L1 inversion showed a better performance over the conventional Tikhonov regularization, TV inversion, and L1 inversion. In the numerical examples, the images reconstructed with TV–L1 inversion were quantitatively more similar to the originating images. In the experimental examples, TV–L1 inversion yielded sharper images and weaker streak artifact. Conclusions: The results herein show that TV–L1 inversion is capable of improving the quality of highly detailed, multiscale optoacoustic images obtained in vivo using cross-sectional imaging systems. As a result of its high fidelity, model-based TV–L1 inversion may be considered as the new standard for image reconstruction in cross-sectional imaging.

60 APPLIED LIFE SCIENCES↗

Accelerated fast iterative shrinkage thresholding algorithms for sparsity-regularized cone-beam CT image reconstruction

Purpose: The development of iterative image reconstruction algorithms for cone-beam computed tomography (CBCT) remains an active and important research area. Even with hardware acceleration, the overwhelming majority of the available 3D iterative algorithms that implement nonsmooth regularizers remain computationally burdensome and have not been translated for routine use in time-sensitive applications such as image-guided radiation therapy (IGRT). In this work, two variants of the fast iterative shrinkage thresholding algorithm (FISTA) are proposed and investigated for accelerated iterative image reconstruction in CBCT. Methods: Algorithm acceleration was achieved by replacing the original gradient-descent step in the FISTAs by a subproblem that is solved by use of the ordered subset simultaneous algebraic reconstruction technique (OS-SART). Due to the preconditioning matrix adopted in the OS-SART method, two new weighted proximal problems were introduced and corresponding fast gradient projection-type algorithms were developed for solving them. We also provided efficient numerical implementations of the proposed algorithms that exploit the massive data parallelism of multiple graphics processing units. Results: The improved rates of convergence of the proposed algorithms were quantified in computer-simulation studies and by use of clinical projection data corresponding to an IGRT study. The accelerated FISTAs were shown to possess dramatically improved convergence properties as compared to the standard FISTAs. For example, the number of iterations to achieve a specified reconstruction error could be reduced by an order of magnitude. Volumetric images reconstructed from clinical data were produced in under 4 min. Conclusions: The FISTA achieves a quadratic convergence rate and can therefore potentially reduce the number of iterations required to produce an image of a specified image quality as compared to first-order methods. We have proposed and investigated accelerated FISTAs for use with two nonsmooth penalty functions that will lead to further reductions in image reconstruction times while preserving image quality. Moreover, with the help of a mixed sparsity-regularization, better preservation of soft-tissue structures can be potentially obtained. The algorithms were systematically evaluated by use of computer-simulated and clinical data sets.

60 APPLIED LIFE SCIENCES↗

Covariance operator estimation: Sparsity, lengthscale, and ensemble Kalman filters

This paper investigates covariance operator estimation via thresholding. For Gaussian random fields with approximately sparse covariance operators, we establish non-asymptotic bounds on the estimation error in terms of the sparsity level of the covariance and the expected supremum of the field. We prove that thresholded estimators enjoy an exponential improvement in sample complexity compared with the standard sample covariance estimator if the field has a small correlation lengthscale. As an application of the theory, we study thresholded estimation of covariance operators within ensemble Kalman filters.

Covariance operator estimation↗

Superresolution via sparsity constraints

The problem of recovering a measure mu supported on a lattice of span Delta is considered under the condition that measurements are only available concerning the Fourier Transform at frequencies of Omega or less. If Omega is much smaller than the Nyquist frequency pi/Delta and the measurements are noisy, then stable recovery of mu is generally impossible. It is shown here that if, in addition, it is known that mu satisfies certain sparsity constraints, then stable recovery is possible. This finding validates practical efforts in spectroscopy, seismic prospecting, and astronomy to provide superresolution by imposing support limitations in reconstruction.

Donoho, David L.↗

Combining Sparsity DEM Inversions with Event Tracking for AIA Data

We introduce a modified version of the ASGARD code (Automated Selection and Grouping of events in A/A Regional Data). Originally written to detect and group brightenings ("events") in the AIA EUV channels, it now includes the sparsity DEM inversion method and instead detects emission measure enhancements in different temperature bins. Ultimately, the goal is to automatically determine heating and cooling rates in different coronal structures.

Bethge, Christian↗

Reduced‐cost sparsity‐exploiting algorithm for solving coupled‐cluster equations

We present an algorithm for reducing the computational work involved in coupled‐cluster (CC) calculations by sparsifying the amplitude correction within a CC amplitude update procedure. We provide a theoretical justification for this approach, which is based on the convergence theory of inexact Newton iterations. We demonstrate by numerical examples that, in the simplest case of the CCD equations, we can sparsify the amplitude correction by setting, on average, roughly 90% nonzero elements to zeros without a major effect on the convergence of the inexact Newton iterations.

Brabec, Jiri↗

Bi-sparsity pursuit: A paradigm for robust subspace recovery

The success of sparse models in computer vision and machine learning is due to the fact that, high dimensional data is distributed in a union of low dimensional subspaces in many real-world applications. The underlying structure may, however, be adversely affected by sparse errors. In this paper, we propose a bi-sparse model as a framework to analyze this problem, and provide a novel algorithm to recover the union of subspaces in the presence of sparse corruptions. We further show the effectiveness of our method by experiments on real-world vision data.

42 ENGINEERING↗