Titles By Year
Abstracts By Year
Technical Reports (2011)
Compressive Sensing for 3D Data Processing Tasks: Applications, Models and Algorithms
Chengbo Li
Compressive sensing (CS) is a novel sampling methodology representing a paradigm shift from conventional data acquisition schemes. The theory of compressive sensing ensures that under suitable conditions compressible signals or images can be reconstructed from far fewer samples or measurements than what are required by the Nyquist rate. So far in the literature, most works on CS concentrate on one-dimensional or two-dimensional data. However, besides involving far more data, three-dimensional (3D) data processing does have particularities that require the development of new techniques in order to make successful transitions from theoretical feasibilities to practical capacities. This thesis studies several issues arising from the applications of the CS methodology to some 3D image processing tasks. Two specific applications are hyperspectral imaging and video compression where 3D images are either directly unmixed or recovered as a whole from CS samples. The main issues include CS decoding models, preprocessing techniques and reconstruction algorithms, as well as CS encoding matrices in the case of video compression.
Our investigation involves three major parts. (1) Total variation (TV) regularization plays a central role in the decoding models studied in this thesis. To solve such models, we propose an efficient scheme to implement the classic augmented Lagrangian multiplier method and study its convergence properties. The resulting Matlab package TVAL3 is used to solve several models. Computational results show that, thanks to its low per-iteration complexity, the proposed algorithm is capable of handling realistic 3D image processing tasks. (2) Hyperspectral image processing typically demands heavy computational resources due to an enormous amount of data involved. We investigate low-complexity procedures to unmix, sometimes blindly, CS compressed hyperspectral data to directly obtain material signatures and their abundance fractions, bypassing the high-complexity task of reconstructing the image cube itself. (3) To overcome the “cliff effect” suffered by current video coding schemes, we explore a compressive video sampling framework to improve scalability with respect to channel capacities. We propose and study a novel multi-resolution CS encoding matrix, and a decoding model with a TV-DCT regularization function.
Extensive numerical results are presented, obtained from experiments that use not only synthetic data but also real data measured by hardware. The results establish feasibility and robustness, to various extent, of the proposed 3D data processing schemes, models and algorithms. There still remain many challenges to be further resolved in each area, but hopefully the progress made in this thesis will represent a useful first step towards meeting these challenges in the future.
December 2011
A Matrix-Free Trust-Region SQP Method for Equality Constrained Optimization
Matthias Heinkenschloss & Denis Ridzal
Abstract TBA
Key Words: Sequential Quadratic Programming, Trust-Region Methods, Large-Scale Optimization, PDE Constrained Optimization
December 2011
Ritz Values of Normal Matrices and Ceva's Theorem
Russell Carden & Derek J. Hansen
The Cauchy interlacing theorem for Hermitian matrices provides an indispensable tool for understanding eigenvalue estimates and various numerical algorithms that rely on the Ritz values of a matrix. No generalization of interlacing is known for non-Hermitian matrices, and as a consequence, many useful algorithms for such matrices are not fully understood. Toward filling this gap, we consider the behavior of Ritz values of normal matrices. We apply Ceva’s theorem, a classical geometric result, to understand two Ritz values of a 3×3 normal matrix and analyze the implications for larger matrices. Unlike the Hermitian case, specifying at most half of the Ritz values significantly restricts where the remaining Ritz values may fall. We use our results to analyze the restarted Arnoldi method with exact shifts applied to a 3 × 3 normal, non-Hermitian matrix.
December 2011
TR11-15 PDF File
Experiments of the Transfer-of-Approximation Finite Element Method and its Basis Localization
Xin Wang & William W. Symes
The transfer-of-approximation, first established by Berlyand and Owhadi (2010) and later generalized by Symes (2011), states that the approximation properties of approximating subspaces for one boundary value problem can be transferred to another. This property immediately implies an application, the transfer-of-approximation finite element method. In it, the regularity of the constant coefficient boundary value problem is transferred into the special finite element space which has the optimal approximation property for the solution of the target variable coefficient problem. Despite of the accuracy property of this non-standard finite element method, the transfer construction applying to practical problems is very expensive: it produces bases with global support, and hence dense stiffness matrices. This report present numerical experiments of the transfer-of-approximation finite element method for both the elliptic boundary value problem and the initial-boundary value problem for the acoustic wave equation, and tests two localization strategies for the transfer basis construction. One is by Owhadi and Zhang (2011) based on the decay of Green’s function with distance. The other is direct truncation of the construction region. Numerical results suggest the transfer-of-approximation finite element method does not appear to achieve optimal order convergence at reasonable expense.
October 2011
Short-Term Recurrence Krylov Subspace Methods for Nearly-Hermitian Matrices
Mark Embree, Josef A. Sifuentes, Kirk M. Soodhalter, Daniel B. Szyld, & Fei Xue
The Progressive GMRES algorithm, introduced by Beckermann and Reichel in 2008, is a residual-minimizing short-recurrence Krylov subspace method for solving a linear system in which the coefficient matrix has a low-rank skew-Hermitian part. We analyze this algorithm, observing a critical instability that makes the method unsuitable for some problems. To work around this issue we introduce a different short-term recurrence method based on Krylov subspaces for such matrices, which can be used as either a solver or a preconditioner. Numerical experiments compare this method to alternative algorithms.
October 2011
The Stability of GMRES Convergence, with Application to Approximate Deflation Preconditioning
Josef A. Sifuentes, Mark Embree, & Ronald B. Morgan
How does GMRES convergence change when the coefficient matrix is perturbed? Using spectral perturbation theory and resolvent estimates, we develop simple, general bounds that quantify the lag in convergence such a perturbation can induce. This analysis is particularly relevant to preconditioned systems, where an ideal preconditioner is only approximately applied in practical computations. To illustrate the utility of this approach, we combine our analysis with Stewart's invariant subspace perturbation theory to develop rigorous bounds on the performance of approximate deflation preconditioning using Ritz vectors.
September 2011
Low-Rank Matrix Recovery using Unconstrained Smoothed-Lq Minimization
Ming-Jun Lai, Yangyang Xu, & Wotao Yin
A low-rank matrix can be recovered from a small number of its linear measurements. As a special case, the matrix completion problem aims to recover the matrix from a subset of its entries. Such problems share many common features with those recovering sparse vectors. In this paper, we extend nonconvex Lq minimization and iteratively reweighted algorithms from recovering sparse vectors to recovering low-rank matrices. Unlike most existing work, this work focuses on unconstrained Lq minimization, for which we show a few advantages on noisy measurements and/or approximately low-rank matrices. Based on results in Daubechies-DeVore-Fornasier-Güntürk '2010 for constrained Lq minimization, we start with a preliminary yet novel analysis for unconstrained Lq minimization for sparse vectors, which includes convergence, error bound, and local convergence rates. Then, the algorithm and analysis is extended to the recovery of low-rank matrices. The algorithm has been compared to some existing state-of-the-arts and shows superior performance on recovering low-rank matrices with fast-decaying singular values from incomplete measurements.
September 2011
Fast Algorithms for Image Reconstruction with Application to Partially Parallel MR Imaging
Y. Chen, W. W. Hager, F. Huang, D. T. Phan, X. Ye, W. Yin
This paper presents two fast algorithms for total variation-based image reconstruction in partially parallel magnetic resonance imaging (PPI) where the inversion matrix is large and ill-conditioned. These algorithms utilize variable splitting techniques to decouple the original problem into more easily solved subproblems. The first method reduces the image reconstruction problem to an unconstrained minimization problem, which is solved by an alternating proximal minimization algorithm. One phase of the algorithm solves a total variation (TV) denoising problem, and second phase solves an ill-conditioned linear system. Linear and sublinear convergence results are given, and an implementation based on a primal-dual hybrid gradient (PDHG) scheme for the TV problem and a Barzilai-Borwein scheme for the linear inversion is proposed. The second algorithm exploits the special structure of the PPI reconstruction problem by decomposing it into one subproblem involving Fourier transforms and another subproblem that can be treated by the PDHG scheme. Numerical results and comparisons with recently developed methods indicate the efficiency of the proposed algorithms.
Key Words: Image reconstruction, Variable splitting, TV denoising, Nonlinear optimization
September 2011
Time-Dependent Coupling of Navier-Stokes and Darcy Flows
A. Cesmelioglu, V. Girault, & B. Riviere
A weak solution of the coupling of time-dependent Navier-Stokes equations with Darcy equations is defined. The interface conditions include the Beavers-Joseph-Saffman condition. Existence and uniqueness of the weak solution are obtained by a constructive approach. The analysis is valid for weak regularity interfaces.
September 2011
Compressive Sensing Based High Resolution Channel Estimation for OFDM System
Jia (Jasmine) Meng, Wotao Yin, Yingying Li, Nam T. Nguyen, and Zhu Han
Orthogonal frequency division multiplexing (OFDM) is a technique that will prevail in the next generation wireless communication. Channel estimation is one of the key challenges in OFDM, since high-resolution channel estimation can significantly improve the equalization at the receiver and consequently enhance the communication performances. In this paper, we propose a system with an asymmetric DAC/ADC pair and formulate OFDM channel estimation as a compressive sensing problem. By skillfully designing pilots and taking advantages of the sparsity of the channel impulse response, the proposed system realizes high resolution channel estimation at a low cost. The pilot design, the use of a high-speed DAC and a regular-speed ADC, and the estimation algorithm tailored for channel estimation distinguish the proposed approach from the existing estimation approaches. We theoretically show that in the proposed system, an N-resolution channel can be faithfully obtained with an ADC speed at M=O(S^2 log(N/S)), where N is also the DAC speed and S is the channel impulse response sparsity. Since S is small and increasing the DAC speed to N>M is relatively cheap, we obtain a high-resolution channel at a low cost. We also present a novel estimator that is both faster and more accurate than the typical L1 minimization. In the numerical experiments, we simulated various numbers of multipaths and different SNRs and let the transmitter DAC run at 16 times the speed of the receiver ADC for estimating channels at the 16x resolution. While there is no similar approaches (for asymmetric DAC/ADC pairs) to compare with, we derive the Cramer-Rao lower bound.
August 2011
Nonlinear Model Reduction via Discrete Empirical Interpolation
Saifon Chaturantabut
This thesis proposes a model reduction technique for nonlinear dynamical systems based upon combining Proper Orthogonal Decomposition (POD) and a new method, called the Discrete Empirical Interpolation Method (DEIM). The popular method of Galerkin projection with POD basis reduces dimension in the sense that far fewer variables are present, but the complexity of evaluating the nonlinear term generally remains that of the original problem. DEIM, a discrete variant of the approach from [11], is introduced and shown to effectively overcome this complexity issue. State space error estimates for POD-DEIM reduced systems are also derived. These L2 error estimates reflect the POD approximation property through the decay of certain singular values and explain how the DEIM approximation error involving the nonlinear term comes into play. An application to the simulation of nonlinear miscible flow in a 2-D porous medium shows that the dynamics of a complex full-order system of dimension 15000 can be captured accurately by the POD-DEIM reduced system of dimension 40 with a factor of O(1000) reduction in computational time.
July 2011
Edge Guided Reconstruction for Compressive Imaging
Weihong Guo & Wotao Yin
We propose EdgeCS -- an edge guided compressive sensing reconstruction approach -- to recover images of higher qualities from fewer measurements than the current state-of-the-art methods. Edges are important images features that are used in various ways in image recovery, analysis, and understanding. In compressive sensing, the sparsity of image edges has been widely utilized to recover images. However, edge detectors have not been used on compressive sensing measurements to improve the edge recovery and thus the image recovery. This motivates us to propose EdgeCS, which alternatively performs edge detection and image reconstruction in a mutually beneficial way. The edge detector of EdgeCS is designed to return partial edges of intermediate image reconstructions, which have excessive noise and artifacts. For complex-valued images, it incorporates joint sparsity between the real and imaginary components.
EdgeCS has been implemented with both isotropic and anisotropic discretizations of total variation and tested on incomplete k-space (Fourier) samples. It applies to other types of measurements as well. Experimental results on large-scale real/complex- valued phantom and magnetic resonance (MR) images show that EdgeCS is fast and returns high-quality images. For example, it exactly recovers the 256-by-256 Shepp-Logan phantom from merely 7 radial lines (3.03% k-space), which is impossible for most existing algorithms. It is able to accurately reconstruct a 512-by-512 MR image with 0.05 white noise from 20.87% radial samples. On complex-valued MR images, it obtains recoveries with faithful phases, which are important in many medical applications. Each of these tests took around 30 seconds on a standard PC. Finally, the algorithm is GPU friendly.
July 2011
Group Sparse Optimization by Alternating Direction Method
Wei Deng, Wotao Yin, & Yin Zhang
This paper proposes efficient algorithms for group sparse optimization with mixed L21-regularization, which arises from the reconstruction of group sparse signals in compressive sensing, and the group Lasso problem in statistics and machine learning. It is known that encoding the group information in addition to sparsity will lead to better signal recovery/feature selection. The L21-regularization promotes group sparsity, but the resulting problem, due to the mixed-norm structure and possible grouping irregularity, is considered more difficult to solve than the conventional L1-regularized problem. Our approach is based on a variable splitting strategy and the classic alternating direction method (ADM). Two algorithms are presented, one derived from the primal and the other from the dual of the L21-regularized problem. The convergence of the proposed algorithms is guaranteed by the existing ADM theory. General group configurations such as overlapping groups and incomplete covers can be easily handled by our approach. Computational results show that on random problems the proposed ADM algorithms exhibit good efficiency, and strong stability and robustness.
April 2011
Approximate Multi-Parameter Inverse Scattering Using Pseudodifferential Scaling
Rami Nammour
I propose a computationally efficient method to approximate the inverse of the normal operator arising in the multi-parameter linearized inverse problem for reflection seismology in two and three spatial dimensions.
Solving the inverse problem using direct matrix methods like Gaussian elimination is computationally infeasible. In fact, the application of the normal operator requires solving large scale PDE problems. However, under certain conditions, the normal operator is a matrix of pseudodifferential operators. This manuscript shows how to generalize Cramer's rule for matrices to approximate the inverse of a matrix of pseudodifferential operators. Approximating the solution to the normal equations proceeds in two steps:
- First, a series of applications of the normal operator to specific permutations of the right hand side. This step yields a phase-space scaling of the solution. Phase space scalings are scalings in both physical space and Fourier space.
- Second, a correction for the phase space scaling. This step requires applying the normal operator once more.
The cost of approximating the inverse is a few applications of the normal operator (one for one parameter, two for two parameters, six for three parameters).
The approximate inverse is an adequately accurate solution to the linearized inverse problem when it is capable of fitting the data to a prescribed precision. Otherwise, the approximate inverse of the normal operator might be used to precondition Krylov subspace methods in order to refine the data fit.
I validate the method on a linearized version of the Marmousi model for constant density acoustics for the one-parameter problem. For the two parameter problem, the inversion of a variable density acoustics layered model corroborates the success of the proposed method. Furthermore, this example details the various steps of the method. I also apply the method to a 1D section of the Marmousi model to test the behavior of the method on complex two-parameter layered models.
April 2011
Dynamic Compressive Spectrum Sensing for Cognitive Radio Networks
Wotao Yin, Zaiwen Wen, Shuyi Li, Jia (Jasmine) Meng, & Zhu Han
In the recently proposed collaborative compressive sensing, the cognitive radios (CRs) sense the occupied spectrum channels by measuring linear combinations of channel powers, instead of sweeping a set of channels sequentially. The measurements are reported to the fusion center, where the occupied channels are recovered by compressive sensing algorithms. In this paper, we study a method of dynamic compressive sensing, which continuously measures channel powers and recovers the occupied channels in a dynamic environment. While standard compressive sensing algorithms must recover multiple occupied channels, a dynamic algorithm only needs to recover the recent change, which is either a newly occupied channel or a released one. On the other hand, the dynamic algorithm must recover the change just in time. Therefore, we propose a least-squared based algorithm, which is equivalent to l0 minimization. We demonstrate its fast speed and robustness to noise. Simulation results demonstrate effectiveness of the proposed scheme.
January 2011
An Alternating Direction Algorithm for Matrix Completion with Nonnegative Factors
Yangyang Xu, Wotao Yin, Zaiwen Wen, & Yin Zhang
This paper introduces a novel algorithm for the nonnegative matrix factorization and completion problem, which aims to nd nonnegative matrices X and Y from a subset of entries of a nonnegative matrix M so that XY approximates M. This problem is closely related to the two existing problems: nonnegative matrix factorization and low-rank matrix completion, in the sense that it kills two birds with one stone. As it takes advantages of both nonnegativity and low rank, its results can be superior than those of the two problems alone. Our algorithm is applied to minimizing a non-convex constrained least-squares formulation and is based on the classic alternating direction augmented Lagrangian method. Preliminary convergence properties and numerical simulation results are presented. Compared to a recent algorithm for nonnegative random matrix factorization, the proposed algorithm yields comparable factorization through accessing only half of the matrix entries. On tasks of recovering incomplete grayscale and hyperspectral images, the results of the proposed algorithm have overall better qualities than those of two recent algorithms for matrix completion.
January 2011
Augmented Lagrangian Alternating Direction Method for Matrix Separation Based on Low-Rank Factorization
Yuan Shen, Zaiwen Wen, & Yin Zhang
The matrix separation problem aims to separate a low-rank matrix and a sparse matrix from their sum. This problem has recently attracted considerable research attention due to its wide range of potential applications. Nuclear-norm minimization models have been proposed for matrix separation and proved to yield exact separations under suitable conditions. These models, however, typically require the calculation of a full or partial singular value decomposition (SVD) at every iteration that can become increasingly costly as matrix dimensions and rank grow. To improve scalability, in this paper we propose and investigate an alternative approach based on solving a non-convex, low-rank factorization model by an augmented Lagrangian alternating direction method. Numerical studies indicate that the effectiveness of the proposed model is limited to problems where the sparse matrix does not dominate the low-rank one in magnitude, though this limitation can be alleviated by certain data pre-processing techniques. On the other hand, extensive numerical results show that, within its applicability range, the proposed method in general has a much faster solution speed than nuclear-norm minimization algorithms, and often provides better recoverability.
January 2011
A Compressive Sensing and Unmixing Scheme for Hyperspectral Data Processing
Chengbo Li, Ting Sun, Kevin Kelly, & Yin Zhang
Hyperspectral data processing typically demands enormous computational resources in terms of storage, computation and I/O throughputs, especially when real-time processing is desired. In this paper, we investigate a low-complexity scheme for hyperspectral data compression and reconstruction. In this scheme, compressed hyperspectral data are acquired directly by a device similar to the single-pixel camera based on the principle of compressive sensing. To decode the compressed data, we propose a numerical procedure to directly compute the unmixed abundance fractions of given endmembers, completely bypassing high-complexity tasks involving the hyperspectral data cube itself. The reconstruction model is to minimize the total variational of the abundance fractions subject to a pre-processed fidelity equation with a significantly reduced size, and other side constraints. An augmented Lagrangian type algorithm is developed to solve this model. We conduct extensive numerical experiments to demonstrate the feasibility and efficiency of the proposed approach, using both synthetic data and hardware-measured data. Experimental and computational evidence obtained from this study indicates that the proposed scheme has a high potential in real-world applications.
January 2011