Friday, May 13, 2011

CS: Compressive Sensing and 3D Transistors, Group Testing course and more.

You probably have heard of the 3D IC at Intel recently. Here is some studies that seem to have a direct impact on that type of work. Before you read it, just know what is being done works because f is assumed a smooth function of its variables and therefore, picking a random sampling of the parameters into the lumped parameter code is really equivalent to doing the same as what was shown in How to Wow your friends, i.e. project that smooth functions unto random located diracs. As practicing engineers know, most of precomputed tables are generally smooth so this type of method is bound to have a great future given that they understand its limitations.

In printed circuit board (PCB) designs, it is common to split power/ground planes into different partitions, which leads to more crosstalk among signal traces that route crossing a split. It is of general interest to develop a crosstalk model for various geometric parameters. However, the long time required to simulate the structure with any given set of geometric parameters renders general modelling approaches such as interpolation inefficient. In this paper, we develop an empirical model based upon the compressed sensing technique to characterize the crosstalk among traces as a function of geometric parameters. A good agreement between the empirical model and full-wave simulations is observed for various test examples, with an exceptionally small number of samples.

Through-Silicon-Vias (TSVs) are the critical enabling technique for three-dimensional integrated circuits (3D ICs). While there are a few existing works in literature to model the electrical performance of TSVs, they are either for fixed geometry or in lack of accuracy. In this paper, we use compressed sensing technique to model the electrical performance of TSV pairs. Experimental results indicate that with an exceptionally small number of samples, our model has a maximum relative error of 3.94% compared with full-wave simulations over a wide range of geometry parameters and frequencies.

This is a short course on algorithmic combinatorial group testing and applications. The basic setting of the group testing problem is to identify a subset of "positive" items from a huge item population using as few "tests" as possible. The meaning of "positive", "tests" and "items" are dependent on the application. For example, dated back to World War II when the area of group testing started, "items" are blood samples, "positive" means syphilis-positive, and a "test" contains a pool of blood samples which results in a positive outcome if there is at least one sample in the pool positive for syphylis. This basic problem paradigm has found numerous applications in biology, cryptography, networking, signal processing, coding theory, statistical learning theory, data streaming, etc. This short course aims to introduce group testing from a computational view point, where not only the constructions of group testing strategies are of interest, but also the computational efficiency of both the construction and the decoding procedures are studied. We will also briefly introduce the probabilistic method, algorithmic coding theory, and several direct applications of group testing.

while looking for group testing on the Google, I found the following abstract forEngineering Competitive and Query-Optimal Minimal-Adaptive Randomized Group Testing Strategies by Muhammad Azam Sheikh and it seems to provide some insight as to why some adaptive strategy might be good for not so sparse defects. From the abstract:
"...Another main result is related to the design of query-optimal and minimal-adaptive strategies. We have shown that a 2-stage randomized strategy with prescribed success probability can asymptotically achieve the information-theoretic lower bound for d much less than n and growing much slower than n. Similarly, we can approach the entropy lower bound in 4 stages when d = o(n)..."
Finally, here is a paper with only an abstract: A compressive sensing perspective on simultaneous marine acquisition by Hassan MansourHaneet WasonTim Lin and Felix Herrmann. The abstract reads:
The high cost of acquiring seismic data in Marine environments compels the adoption of simultaneous- source acquisition - an emerging technology that is stimulating both geophysical research and commercial efforts. In this paper, we discuss the properties of randomized simultaneous acquisition matrices and demonstrate that sparsity-promoting recovery improves the quality of the reconstructed seismic data volumes. Simultaneous Marine acquisition calls for the development of a new set of design principles and post-processing tools. Leveraging established findings from the field of compressed sensing, the recovery from simultaneous sources depends on a sparsifying transform that compresses seismic data, is fast, and reasonably incoherent with the compressive sampling matrix. To achieve this incoherence, we use random time dithering where sequential acquisition with a single airgun is replaced by continuous acquisition with multiple airguns firing at random times and at random locations. We demonstrate our results with simulations of simultaneous Marine acquisition using periodic and randomized time dithering.

I also found the following poster session at ISMRM conference:
Compressed Sensing & Receive Arrays at ISMRM

 2857 Array Compression for 3D Cartesian Sampling Tao Zhang1, Michael Lustig1,2, Shreyas Vasanawala3, and John Pauly11Electrical Engineering, Stanford University, Stanford, CA, United States, 2Electrical Engineering and Computer Science, University of California Berkeley, Berkeley, CA, United States, 3Radiology, Stanford University, Stanford, CA, United States  Array compression is a technique to reduce data size and reconstruction computation for large coil arrays. In this work, a data-driven array compression for 3D Cartesian sampling is proposed. A slice-by-slice array compression method with autocalibrating parallel reconstruction using 3D synthesis kernels is designed. Faster reconstruction and similar image quality is achieved compared with reconstruction results using the original large arrays. 2858 k-Space Channel Combination for Non-Cartesian Acquisitions Using Direct Virtual Coil (DVC) CalibrationPhilip James Beatty1, Atsushi Takahashi2, Kevin M Johnson3, and Jean H Brittain41Global Applied Science Laboratory, GE Healthcare, Thornhill, Ontario, Canada, 2Global Applied Science Laboratory, GE Healthcare, Menlo Park, California, United States, 3Medical Physics, University of Wisconsin - Madison, Madison, Wisconsin, United States, 4Global Applied Science Laboratory, GE Healthcare, Madison, Wisconsin, United States  k-Space channel combination for multi-channel acquisitions promises to reduce reconstruction latency by combining data across channels during data acquisition and reducing the number of Fourier transforms required for data reconstruction. In this work, a method is proposed that enables k-space channel combination for non-Cartesian acquisitions. The proposed approach combines Direct Virtual Coil (DVC) channel combination calibration with conventional convolution gridding. Image quality is evaluated using radial and spiral data sets. 2859 Compressed Sensing with Compressed ChannelsFeng Huang1, Wei Lin1, George Randy Duensing1, and Arne Reykowski11Invivo Corporation, Gainesville, Florida, United States  In MRI, imaging using receiving coil arrays with a large number of elements is an area of growing interest. With increasing channel numbers, longer reconstruction times have become a significant concern. Channel compression has been proposed to reduce the processing time. However, channel compression technique has to balance speed and preservation of signal. In this work, a novel technique using relative sensitivity maps is proposed for faster channel-by-channel compressed sensing. The proposed method is much faster than conventional channel compression technique, and preserves the signal significantly better. 2860 GRAPPA Operator Enhanced Initialization for Improved Multi-channel Compressed SensingFeng Huang1, Wei Lin1, George Randy Duensing1, and Arne Reykowski11Invivo Corporation, Gainesville, Florida, United States  The combination of partially parallel imaging (PPI) and compressed sensing has shown great potential for fast imaging. Fourier transform of the partially acquired data is conventionally used as the initialization of the iterative reconstruction algorithm. A good initialization is crucial for the convergence speed and accuracy of iterative algorithms. In this work, it is proposed to use GRAPPA operator to efficiently generate initialization for multi-channel compressed sensing. Using self-feeding Sparse SENSE as a specific example of multi-channel compressed sensing algorithm, experimental results show the advantages of the proposed method over conventional scheme. 2861 SpRING: Sparse Reconstruction of Images using the Nullspace method and GRAPPADaniel Stuart Weller1, Jonathan R Polimeni2,3, Leo Grady4, Lawrence L Wald2,3, Elfar Adalsteinsson1, and Vivek Goyal11EECS, Massachusetts Institute of Technology, Cambridge, MA, United States, 2A. A. Martinos Center, Dept. of Radiology, Massachusetts General Hospital, Charlestown, MA, United States, 3Dept. of Radiology, Harvard Medical School, Boston, MA, United States, 4Dept. of Image Analytics and Informatics, Siemens Corporate Research, Princeton, NJ, United States  SpRING combines compressed sensing (CS) with GRAPPA to recover a sparse image from multi-channel, undersampled k-space data. The combined method operates in the nullspace of the observation matrix, holding the acquired data fixed without resorting to complicated procedures for constrained optimization. Whereas GRAPPA amplifies the noise present in the image and CS over-smoothes non-sparse details, the combined method strikes a balance to improve SNR and preserve details. We analyze the noise amplification properties of the combined algorithm using g-factors computed using Monte Carlo trials to illustrate its superiority over GRAPPA and CS alone for real data. 2862 A Method to Combine Compressed Sensing with Auto-Calibrating Parallel Imaging Reconstruction for Cartesian AcquisitionKang Wang1, Philip Beatty2, James Holmes2, Reed Busse2, Jean Brittain2, and Frank Korosec11Medical Physics, University of Wisconsin-Madison, Madison, WI, United States, 2Global Applied Science Laboratory, GE Healthcare  This abstract presents a framework that combines compressed sensing (CS) with auto-calibration parallel imaging (acPI) reconstruction for undersampled Cartesian acquisition. In data acquisition, a two-step undersampling scheme is used. For reconstruction, an acPI method is integrated into the CS L1 norm minimization process, such that both the coherent and incoherent aliasing artifacts associated with the undersampling can be suppressed in the iteration. The feasibility of the new method was validated using 3D contrast-enhanced peripheral MR angiography data sets 2863 Impact of Coil-Neighbors of Target points in Autocalibration of ESPIRiTAnja Brau1, Peng Lai1, Srihari Narasimhan2, Babu Narayanan3, and Vijaya Saradhi21Global Applied Science Laboratory, GE Healthcare, Menlo Park, CA, United States, 2Computing & Decision Sciences Lab, GE Global Research, Bangalore, India, 3Medical Image Analysis Lab, GE Global Research, Bangalore, India  As part of the calibration step for Compressed Sensing & Parallel Imaging algorithms like ESPIRiT and L1-SPIRiT, computation of kernel weights involves obtaining a least squares fit for predicting target points in the calibration region using a set of source points in their neighborhood, separately for each coil. If we do not use the coil neighbors of the target location, the linear system needs to be solved only once. We observe that using this approach, we get significant computational benefit and still obtain similar image quality for high channel count reconstructions. 2864 CS-SENSE Reconstruction Using a Two-level Variable Density Sampling PatternMariya Doneva1,2, Peter Börnert1, and Alfred Mertins21Philips Research Europe, Hamburg, Germany, 2University of Luebeck, Luebeck, Germany  The synthesis of CS and parallel imaging is of consierable interest. Several works have proposed a combination of SENSE and CS as an iterative sparsity constrained SENSE reconstruction. Typically a variable density pseudo-random sampling is used as a compromise between regular and irregular sampling. Based on the properties of CS and SENSE, we propose a two-step CS-SENSE reconstruction, in which the two reconstruction steps are used to recover distinct parts of k-space and apply a two-level variable density sampling pattern. 2865 Single-signal Based Parallel Imaging Using Compressed Sensingsatoshi Ito1, Hirotoshi Arai1, and Yoshifumi Yamada11Research Division of Intelligence and Information Sciencs, Utsunomiya University, Utsunomiya, Tochigi, Japan  In this paper, we propose a novel image reconstruction method in which CS and PI are executed using only single set of signal. Since the distribution of PSFT signal strongly reflects the distribution of the object, the application of a weighting function to the PSFT signals has a similar effect as the application of the weighting function to the object. Therefore SENSE reconstruction using a single signal is feasible by producing another folded image having another weighting function. Here, we propose a new imaging method which combine CS and PI using single signal to achieve higher reduction factor. 2866 Parallel Compressed Sensing MRI Using Reweighted L1 MinimizationChing-hua Chang1, and Jim Ji11Texas A&M University, College Station, Texas, United States  The combination of Compressed Sensing (CS) with multiple receiver coils has drawn great attentions because of their potentials to significantly reduce acquisition time in MRI. The former emerged by exploring the sparsity of MR images, and the latter can reduce scan time by resorting to parallel MRI (pMRI). CS can be used as regularization method and is integrated to take advantages of the sensitivity information from multiple receiver coils. In this abstract, we propose to use a reweighted nonlinear conjugate gradient L1 minimization method to enhance the reconstruction of parallel CS-MRI.