Technical Reports (2012)
The Neural Computations in Spatial Memory From Single Cells to Networks
Kathryn Ruth Hedrick
Studies of spatial memory provide valuable insight into more general mnemonic functions, for by observing the activity of cells such as place cells, one can follow a subject’s dynamic representation of a changing environment. I investigate how place cells resolve conflicting neuronal input signals by developing computational models that integrate synaptic inputs on two scales. First, I construct reduced models of morphologically accurate neurons that preserve neuronal structure and the spatial specificity of inputs. Second, I use a parallel implementation to examine the dynamics among a network of interconnected place cells. Both models elucidate possible roles for the inputs and mechanisms involved in spatial memory.
Place cells combine spatial information carried by afferents from the medial entorhinal cortex (MEC) with contextual information carried by afferents from the lateral entorhinal cortex (LEC). Studies indicate that the structured distribution of synapses on the dendrites affects how place cells integrate input from MEC, LEC, and neighboring place cells. However, models mapping spatially distributed inputs to the somatic potential are computationally expensive, and existing reduced models sacrifice either the spatial component of the input signal or the electrophysiology of the original model. I use Krylov subspace projection methods to construct reduced models of passive and quasi-active neurons that accurately reproduce the somatic potential, preserve the spatial specificity of inputs and the underlying circuit structure, and are constructed from straightforward transformations dependent on intrinsic dendritic properties. The accuracy, efficiency, and electrophysiological interpretation of the reduced models render them useful in examining dendritic computations.
I further develop a computational platform to study the dynamics among a network of isopotential place cells as a learned environment is modified, placing LEC and MEC inputs in conflict. The experimental paradigm on which the model is based allows me to directly test the respective roles of each input group as well as the mechanisms affecting how place cells resolve the competition in their input signals. Using both the reduced and network models, I demonstrate that accepted mechanisms, such as synaptic plasticity and cell assembly dynamics, can combine in non-intuitive ways to govern the place cell representation of a modified environment.
April 2012
An Approach for the Adaptive Solution of Optimization Problems Governed by Partial Differential Equations with Uncertain Coefficients
Drew P. Kouri
In this thesis, I develop and analyze a general theoretical framework for optimization problems governed by partial differential equations (PDEs) with random inputs. This theoretical framework is based on the adjoint calculus for computing derivatives of the objective function. I develop an efficient discretization and numerical optimization algorithm for the solution of these PDE constrained optimization problems. Using derivative based numerical optimization algorithms to solve these PDE constrained optimization problems is computationally expensive due to the large number of PDE solves required at each iteration. I present a stochastic collocation discretization for these PDE constrained optimization problems and prove the convergence of this discretization method for a specific class of problems
The stochastic collocation discretization technique described here requires many decoupled PDE solves to compute gradient and Hessian information. I develop a novel optimization theoretic framework based on dimension adaptive sparse grid quadrature to reduce the total number of PDE solves. My adaptive framework employs basic or retrospective trust regions to manage the adapted stochastic collocation models. In addition, I prove global first order convergence of the retrospective trust region algorithm under weakened assumptions on the modeled gradients. In fact, if one can bound the error between actual and modeled gradients using reliable and efficient a posteriori error estimators, then the global convergence of the retrospective trust region algorithm follows.
Finally, I describe a high performance implementation of my adaptive collocation and trust region framework. This framework can be efficiently implemented in the C++ programming language using the Message Passing Interface (MPI). Due to the large number of PDE solves required for derivative computations, it is essential to choose inexpensive approximate models and appropriate large-scale nonlinear programming techniques throughout the optimization routine to obtain an efficient algorithm. Numerical results for the adaptive solution of these optimization problems are presented.
April 2012
Penalty-Free Discontinuous Galerkin Methods for Incompressible Navier-Stokes Equations
Beatrice Riviere & Shirin Sardar
A first-order discontinuous Galerkin method is proposed for solving the steady-state incompressible Navier-Stokes equations. The stability of this penalty-free method is obtained by locally enriching the discrete space with a quadratic polynomial. A priori error estimates are derived. Numerical examples confirm the theoretical convergence.
April 2012
TR12-08 PDF File
A Nonlinear Differential Semblance Algorithm for Waveform Inversion
Dong Sun
This paper presents a nonlinear differential semblance approach to waveform inversion. The tradition least squares approach cannot guarantee a reliable solution, because of the existence of many spurious local minima of the objective function for typical data, which lacks low-frequency energy. Nonlinear differential semblance optimization combines the ability of full waveform inversion to account for nonlinear physical effects, such as multiple reflections, with the tendency of differential semblance migration velocity analysis to avoid local minima. It borrows the gather-flattening concept from migration velocity analysis, and updates the velocity by flattening primaries-only gathers obtained via nonlinear inversion.
This paper describes a general formulation of this algorithm, its components, including the gradient calculation, and its implementation. We present some numerical experiments based on 2D plane wave modeling in a simple layered media, whereas nonlinear differential semblance succeeds in constructing a kinematically correct model and fitting the data rather precisely.
March 2012
Limited Memory Block Krylov Subspace Optimization for Computing Dominant Singular Value Decompositions
Xin Liu, Zaiwen Wen, & Yin Zhang
In many data-intensive applications, the use of principal component analysis (PCA) and other related techniques is ubiquitous for dimension reduction, data mining or other transformational purposes. Such transformations often require efficiently, reliably and accurately computing dominant singular value decompositions (SVDs) of large unstructured matrices. In this paper, we propose and study a subspace optimization technique to significantly accelerate the classic simultaneous iteration method. We analyze the convergence of the proposed algorithm, and numerically compare it with several state-of-the-art SVD solvers under the MATLAB environment. Extensive computational results show that on a wide range of large unstructured matrices, the proposed algorithm can often provide improved efficiency or robustness over existing algorithms.
Key Words: subspace optimization, dominant singular value decomposition, Krylov subspace, eigenvalue decomposition
March 2012
Decentralized Jointly Sparse Optimization by Reweighted Lq Minimization
Qing Ling, Zaiwen Wen, & Wotao Yin
A set of vectors (or signals) are jointly sparse if their nonzero entries are commonly supported on a small subset of locations. Consider a network of agents which collaborative recover a set of joint sparse vectors. This paper proposes novel decentralized algorithms to recover these vectors in a way that every agent runs a recovery algorithm while neighbor agents exchange only their estimates of the joint support but not their data. The agents will obtain their solutions by taking advantages of the joint sparse structure while keeping their data private. As such, the proposed approach finds applications in distributed (compressive) sensing, decentralized event detection, as well as collaborative data mining. We use a non-convex minimization model and propose algorithms that alternate between support estimate consensus and signal estimate update. The latter step is based on reweighted Lq iterations, where q can be 1 or 2. We numerically compare the proposed decentralized algorithms with existing centralized and decentralized algorithms. Simulation results demonstrate that the proposed decentralized approaches have strong recovery performance and converge reasonably fast.
February 2012
Learning a Circulant Sensing Matrix
Yangyang Xu, Wotao Yin, Susan Chen, & Stanley Osher
In signal acquisition, Toeplitz and circulant matrices are widely used as sensing operators since they can be easily or even naturally realized in various applications. For compressive sensing, recent work has used random Toeplitz and circulant sensing matrices and proved their e ciency in theory, by computer simulations, as well as through physical optical experiments.
Motivated by recent work [7], we propose models to optimize a circulant sensint matrix. Given the dictionary of the signal(s) to be sensed, the optimized circulant sensing matrix is more e ective than a randomly generated circulant sensing matrix, and even a Gaussian random sensing matrix. In addition, we test learning the circulant sensing matrix and the nonparametric dictionary altogether and obtain even better performance on encoding and decoding test signals. We demonstrate these results using both synthetic sparse signals and real images.
January 2012
Structure-Preserving Model Reduction of Passive and Quasi-Active Neurons
Kathryn Hedrick & Steven J. Cox
The spatial component of input signals often carries information crucial to a neuron's function, but models which map synaptic inputs to the transmembrane potential can be computationally expensive. Existing reduced models of the neuron either merge compartments, thereby sacrificing the spatial specificity of inputs, or apply model reduction techniques which sacrifice the biological interpretation of the model. We use Krylov subspace projection methods to construct reduced models of the passive and quasi-active neurons which preserve both the spatial specificity of inputs and the biological interpretation as an RC and RLC circuit, respectively. Each reduced model accurately computes the potential at the spike initiation zone (siz) given a much smaller dimension and simulation time, as we show numerically and theoretically. The structure is preserved through the similarity in the circuit representations, for which we provide circuit diagrams and mathematical expressions for the circuit elements. Furthermore, the transformation from the full to the reduced system is straightforward and depends on the intrinsic properties of the dendrite. As each reduced model is accurate and has a clear biological interpretation, the reduced models can be used not only to simulate morphologically accurate neurons but also to examine the underlying functions performed in dendrites.
January 2012
Error Forgetting of Bregman Iteration
Wotao Yin & Stanley Osher
This short article analyzes an interesting property of the Bregman iterative procedure for minimizing a convex piece-wise linear function J(x) subject to linear constraints Ax=b. The procedure obtains its solution by solving a sequence of unconstrained subproblems, each minimizing J(x) + (1/2) ||Ax-bk||2, and iteratively updating bk. In practice, the subproblems are solved with finite accuracy. Let wk denote the numerical error at iteration k. If all wk are sufficiently small, Bregman iteration identifies the optimal face in finitely many iterations, and afterward, it enjoys an interesting error-forgetting property: the distance between the current point and the optimal solution set is bounded by ||wk+1-wk||, independent of the numerical errors at previous iterations. This property partially explains why the Bregman iterative procedure works well for sparse optimization and ||x||1 minimization. The error-forgetting property is unique to piece-wise linear functions (i.e., polyhedral functions) J(x), and it is new to the literature of the augmented Lagrangian method.
January 2012
Augmented L1 and Nuclear-Norm Models with a Globally Linearly Convergent Algorithm
Ming-Jun Lai & Wotao Yin
This paper studies the models of minimizing $||x||_1+1/(2\alpha)||x||_2^2$ where $x$ is a vector, as well as those of minimizing $||X||_*+1/(2\alpha)||X||_F^2$ where $X$ is a matrix and $||X||_*$ and $||X||_F$ are the nuclear and Frobenius norms of $X$, respectively. We show that they can efficiently recover sparse vectors and low-rank matrices. In particular, they enjoy exact and stable recovery guarantees similar to those known for minimizing $||x||_1$ and $||X||_*$ under the conditions on the sensing operator such as its null-space property, restricted isometry property, spherical section property, or RIPless property. To recover a (nearly) sparse vector $x^0$, minimizing $||x||_1+1/(2\alpha)||x||_2^2$ returns (nearly) the same solution as minimizing $||x||_1$ almost whenever $\alpha\ge 10||x^0||_\infty$. The same relation also holds between minimizing $||X||_*+1/(2\alpha)||X||_F^2$ and minimizing $||X||_*$ for recovering a (nearly) low-rank matrix $X^0$, if $\alpha\ge 10||X^0||_2$. Furthermore, we show that the linearized Bregman algorithm for minimizing $||x||_1+1/(2\alpha)||x||_2^2$ subject to $Ax=b$ enjoys global linear convergence as long as a nonzero solution exists, and we give an explicit rate of convergence. The convergence property does not require a solution solution or any properties on $A$. To our knowledge, this is the best known global convergence result for first-order sparse optimization algorithms.
January 2012
Ritz Value Localization for Non-Hermitian Matrices
Mark Embree & Russell Carden
Rayleigh–Ritz eigenvalue estimates for Hermitian matrices obey Cauchy interlacing, which has helpful implications for theory, applications, and algorithms. In contrast, few results about the Ritz values of non-Hermitian matrices are known, beyond the containment of these values within the numerical range. To show that such Ritz values enjoy considerable structure, we establish regions within the numerical range in which the various Ritz values of general matrices must be contained. To demonstrate that localization occurs even for extreme examples, we carefully analyze possible Ritz value combinations for a three-dimensional Jordan block.
Key Words: Ritz values, numerical range, inverse field of values problem
January 2012