A QUBO Algorithm to Compute Eigenvectors of Symmetric Matrices

• URL: http://arxiv.org/abs/2104.11311v1
• Date: Thu, 22 Apr 2021 20:41:57 GMT
• Title: A QUBO Algorithm to Compute Eigenvectors of Symmetric Matrices
• Authors: Benjamin Krakoff, Susan M. Mniszewski, Christian F. A. Negre
• Abstract summary: We describe an algorithm to compute the extremal eigenvalues and corresponding eigenvectors of a symmetric matrix by solving a sequence of Quadratic Binary Optimization problems. This algorithm is robust across many different classes of symmetric matrices, can compute the eigenvector/eigenvalue pair to essentially arbitrary precision, and with minor modifications can also solve the generalized eigenvalue problem.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We describe an algorithm to compute the extremal eigenvalues and corresponding eigenvectors of a symmetric matrix by solving a sequence of Quadratic Binary Optimization problems. This algorithm is robust across many different classes of symmetric matrices, can compute the eigenvector/eigenvalue pair to essentially arbitrary precision, and with minor modifications can also solve the generalized eigenvalue problem. Performance is analyzed on small random matrices and selected larger matrices from practical applications.

Related papers

• Resolvent-based quantum phase estimation: Towards estimation of parametrized eigenvalues [0.0]
  We propose a novel approach for estimating the eigenvalues of non-normal matrices based on the matrix resolvent formalism. We construct the first efficient algorithm for estimating the phases of the unit-norm eigenvalues of a given non-unitary matrix. We then construct an efficient algorithm for estimating the real eigenvalues of a given non-Hermitian matrix.
  arXiv  Detail & Related papers  (2024-10-07T08:51:05Z)
• Bounding Real Tensor Optimizations via the Numerical Range [0.0]
  We show how the numerical range of a matrix can be used to bound the optimal value of certain optimization problems over real tensor product vectors. Our bound is stronger than the trivial bounds based on eigenvalues, and can be computed significantly faster than bounds provided by semidefinite programming relaxations.
  arXiv  Detail & Related papers  (2022-12-24T20:03:06Z)
• The Hypervolume Indicator Hessian Matrix: Analytical Expression, Computational Time Complexity, and Sparsity [4.523133864190258]
  This paper establishes the analytical expression of the Hessian matrix of the mapping from a (fixed size) collection of $n$ points in the $d$-dimensional decision space to the scalar hypervolume indicator value. The Hessian matrix plays a crucial role in second-order methods, such as the Newton-Raphson optimization method, and it can be used for the verification of local optimal sets.
  arXiv  Detail & Related papers  (2022-11-08T11:24:18Z)
• A quantum algorithm for solving eigenproblem of the Laplacian matrix of a fully connected weighted graph [4.045204834863644]
  We propose an efficient quantum algorithm to solve the eigenproblem of the Laplacian matrix of a fully connected weighted graph. Specifically, we adopt the optimal Hamiltonian simulation technique based on the block-encoding framework. We also show that our algorithm can be extended to solve the eigenproblem of symmetric (non-symmetric) normalized Laplacian matrix.
  arXiv  Detail & Related papers  (2022-03-28T02:24:08Z)
• Robust 1-bit Compressive Sensing with Partial Gaussian Circulant Matrices and Generative Priors [54.936314353063494]
  We provide recovery guarantees for a correlation-based optimization algorithm for robust 1-bit compressive sensing. We make use of a practical iterative algorithm, and perform numerical experiments on image datasets to corroborate our results.
  arXiv  Detail & Related papers  (2021-08-08T05:28:06Z)
• Non-PSD Matrix Sketching with Applications to Regression and Optimization [56.730993511802865]
  We present dimensionality reduction methods for non-PSD and square-roots" matrices. We show how these techniques can be used for multiple downstream tasks.
  arXiv  Detail & Related papers  (2021-06-16T04:07:48Z)
• Adversarially-Trained Nonnegative Matrix Factorization [77.34726150561087]
  We consider an adversarially-trained version of the nonnegative matrix factorization. In our formulation, an attacker adds an arbitrary matrix of bounded norm to the given data matrix. We design efficient algorithms inspired by adversarial training to optimize for dictionary and coefficient matrices.
  arXiv  Detail & Related papers  (2021-04-10T13:13:17Z)
• Analysis of Truncated Orthogonal Iteration for Sparse Eigenvector Problems [78.95866278697777]
  We propose two variants of the Truncated Orthogonal Iteration to compute multiple leading eigenvectors with sparsity constraints simultaneously. We then apply our algorithms to solve the sparse principle component analysis problem for a wide range of test datasets.
  arXiv  Detail & Related papers  (2021-03-24T23:11:32Z)
• Quantum query complexity with matrix-vector products [9.192149087264033]
  We study quantum algorithms that learn properties of a matrix using queries that return its action on an input vector. We show that for various problems, including computing the trace, determinant or rank of a matrix, quantum computers do not provide an speedup over classical computation.
  arXiv  Detail & Related papers  (2021-02-22T20:42:17Z)
• Eigendecomposition-Free Training of Deep Networks for Linear Least-Square Problems [107.3868459697569]
  We introduce an eigendecomposition-free approach to training a deep network. We show that our approach is much more robust than explicit differentiation of the eigendecomposition. Our method has better convergence properties and yields state-of-the-art results.
  arXiv  Detail & Related papers  (2020-04-15T04:29:34Z)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  We study the performance of iterative sketching for least-squares problems. We show that the convergence rate for Haar and randomized Hadamard matrices are identical, andally improve upon random projections. These techniques may be applied to other algorithms that employ randomized dimension reduction.
  arXiv  Detail & Related papers  (2020-02-03T16:17:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.