Throughout many scientific and engineering fields, including control theory, quantum mechanics, advanced dynamics, and network theory, a great many important applications rely on the spectral decomposition of matrices. Traditional methods such as the power iteration method, Jacobi eigenvalue method, and QR decomposition are commonly used to compute the eigenvalues and eigenvectors of a square and symmetric matrix. However, these methods suffer from certain drawbacks: in particular, the power iteration method can only find the leading eigen-pair (i.e., the largest eigenvalue and its corresponding eigenvector), while the Jacobi and QR decomposition methods face significant performance limitations when facing with large scale matrices. Typically, even producing approximate eigenpairs of a general square matrix requires at least O(N^3) time complexity, where N is the number of rows of the matrix. In this work, we exploit the newly developed memristor technology to propose a low-complexity, scalable memristor-based method for deriving a set of dominant eigenvalues and eigenvectors for real symmetric non-negative matrices. The time complexity for our proposed algorithm is O(N^2 /Δ) (where Δ governs the accuracy). We present experimental studies to simulate the memristor-supporting algorithm, with results demonstrating that the average error for our method is within 4%, while its performance is up to 1.78X better than traditional methods.
more »
« less
Memory-Efficient Learning of Stable Linear Dynamical Systems for Prediction and Control
Learning a stable Linear Dynamical System (LDS) from data involves creating
models that both minimize reconstruction error and enforce stability of the learned
representation. We propose a novel algorithm for learning stable LDSs. Using
a recent characterization of stable matrices, we present an optimization method
that ensures stability at every step and iteratively improves the reconstruction
error using gradient directions derived in this paper. When applied to LDSs
with inputs, our approach—in contrast to current methods for learning stable
LDSs—updates both the state and control matrices, expanding the solution space
and allowing for models with lower reconstruction error. We apply our algorithm
in simulations and experiments to a variety of problems, including learning
dynamic textures from image sequences and controlling a robotic manipulator.
Compared to existing approaches, our proposed method achieves an orders-of-magnitude improvement in reconstruction error and superior results in terms of
control performance. In addition, it is provably more memory efficient, with
an O(n2) space complexity compared to O(n4) of competing alternatives, thus
scaling to higher-dimensional systems when the other methods fail. The code
of the proposed algorithm and animations of the results can be found at https:
//github.com/giorgosmamakoukas/MemoryEfficientStableLDS.
more »
« less
- Award ID(s):
- 1717951
- NSF-PAR ID:
- 10302017
- Date Published:
- Journal Name:
- Advances in neural information processing systems
- ISSN:
- 1049-5258
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
more » « less
Purpose To develop an improved k‐space reconstruction method using scan‐specific deep learning that is trained on autocalibration signal (ACS) data.
Theory Robust artificial‐neural‐networks for k‐space interpolation (RAKI) reconstruction trains convolutional neural networks on ACS data. This enables nonlinear estimation of missing k‐space lines from acquired k‐space data with improved noise resilience, as opposed to conventional linear k‐space interpolation‐based methods, such as GRAPPA, which are based on linear convolutional kernels.
Methods The training algorithm is implemented using a mean square error loss function over the target points in the ACS region, using a gradient descent algorithm. The neural network contains 3 layers of convolutional operators, with 2 of these including nonlinear activation functions. The noise performance and reconstruction quality of the RAKI method was compared with GRAPPA in phantom, as well as in neurological and cardiac in vivo data sets.
Results Phantom imaging shows that the proposed RAKI method outperforms GRAPPA at high (≥4) acceleration rates, both visually and quantitatively. Quantitative cardiac imaging shows improved noise resilience at high acceleration rates (rate 4:23% and rate 5:48%) over GRAPPA. The same trend of improved noise resilience is also observed in high‐resolution brain imaging at high acceleration rates.
Conclusion The RAKI method offers a training database‐free deep learning approach for MRI reconstruction, with the potential to improve many existing reconstruction approaches, and is compatible with conventional data acquisition protocols.
-
We demonstrate that with an optimally tuned scheduling function, adiabatic quantum computing (AQC) can readily solve a quantum linear system problem (QLSP) with O (κ poly(log (κ ε))) runtime, where κ is the condition number, and ε is the target accuracy. This is near optimal with respect to both κ and ε, and is achieved without relying on complicated amplitude amplification procedures that are difficult to implement. Our method is applicable to general non-Hermitian matrices, and the cost as well as the number of qubits can be reduced when restricted to Hermitian matrices, and further to Hermitian positive definite matrices. The success of the time-optimal AQC implies that the quantum approximate optimization algorithm (QAOA) with an optimal control protocol can also achieve the same complexity in terms of the runtime. Numerical results indicate that QAOA can yield the lowest runtime compared to the time-optimal AQC, vanilla AQC, and the recently proposed randomization method.more » « less
-
Hardware accelerations of deep learning systems have been extensively investigated in industry and academia. The aim of this paper is to achieve ultra-high energy efficiency and performance for hardware implementations of deep neural networks (DNNs). An algorithm-hardware co-optimization framework is developed, which is applicable to different DNN types, sizes, and application scenarios. The algorithm part adopts the general block-circulant matrices to achieve a fine-grained tradeoff of accuracy and compression ratio. It applies to both fully-connected and convolutional layers and contains a mathematically rigorous proof of the effectiveness of the method. The proposed algorithm reduces computational complexity per layer from O(n2 ) to O(n log n) and storage complexity from O(n2) to O(n), both for training and inference. The hardware part consists of highly efficient Field Programmable Gate Array (FPGA)-based implementations using effective reconfiguration, batch processing, deep pipelining, resource re-using, and hierarchical control. Experimental results demonstrate that the proposed framework achieves at least 152X speedup and 71X energy efficiency gain compared with IBM TrueNorth processor under the same test accuracy. It achieves at least 31X energy efficiency gain compared with the reference FPGA-based work.more » « less
-
more » « less
Abstract This article presents high order accurate discontinuous Galerkin (DG) methods for wave problems on moving curved meshes with general choices of basis and quadrature. The proposed method adopts an arbitrary Lagrangian–Eulerian formulation to map the wave equation from a time‐dependent moving physical domain onto a fixed reference domain. For moving curved meshes, weighted mass matrices must be assembled and inverted at each time step when using explicit time‐stepping methods. We avoid this step by utilizing an easily invertible weight‐adjusted approximation. The resulting semi‐discrete weight‐adjusted DG scheme is provably energy stable up to a term that (for a fixed time interval) converges to zero with the same rate as the optimal error estimate. Numerical experiments using both polynomial and B‐spline bases verify the high order accuracy and energy stability of proposed methods.
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
