A fixed-point algorithm for matrix projections with applications in quantum information

• URL: http://arxiv.org/abs/2312.14615v2
• Date: Tue, 12 Mar 2024 08:51:41 GMT
• Title: A fixed-point algorithm for matrix projections with applications in quantum information
• Authors: Shrigyan Brahmachari, Roberto Rubboli, and Marco Tomamichel
• Abstract summary: We show that our algorithm converges exponentially fast to the optimal solution in the number of iterations. We discuss several applications of our algorithm in quantum resource theories and quantum Shannon theory.
• Score: 7.988085110283119
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We develop a simple fixed-point iterative algorithm that computes the matrix projection with respect to the Bures distance on the set of positive definite matrices that are invariant under some symmetry. We prove that the fixed-point iteration algorithm converges exponentially fast to the optimal solution in the number of iterations. Moreover, it numerically shows fast convergence compared to the off-the-shelf semidefinite program solvers. Our algorithm, for the specific case of matrix barycenters, recovers the fixed-point iterative algorithm originally introduced in (\'Alvarez-Esteban et al., 2016). Compared to previous works, our proof is more general and direct as it is based only on simple matrix inequalities. Finally, we discuss several applications of our algorithm in quantum resource theories and quantum Shannon theory.

Related papers

• Bregman-divergence-based Arimoto-Blahut algorithm [53.64687146666141]
  We generalize the Arimoto-Blahut algorithm to a general function defined over Bregman-divergence system. We propose a convex-optimization-free algorithm that can be applied to classical and quantum rate-distortion theory.
  arXiv  Detail & Related papers  (2024-08-10T06:16:24Z)
• A Catalyst Framework for the Quantum Linear System Problem via the Proximal Point Algorithm [9.804179673817574]
  We propose a new quantum algorithm for the quantum linear system problem (QLSP) inspired by the classical proximal point algorithm (PPA) Our proposed method can be viewed as a meta-algorithm that allows inverting a modified matrix via an existing texttimattQLSP_solver. By carefully choosing the step size $eta$, the proposed algorithm can effectively precondition the linear system to mitigate the dependence on condition numbers that hindered the applicability of previous approaches.
  arXiv  Detail & Related papers  (2024-06-19T23:15:35Z)
• Tensor networks based quantum optimization algorithm [0.0]
  In optimization, one of the well-known classical algorithms is power iterations. We propose a quantum realiziation to circumvent this pitfall. Our methodology becomes instance agnostic and thus allows one to address black-box optimization within the framework of quantum computing.
  arXiv  Detail & Related papers  (2024-04-23T13:49:11Z)
• Learning the Positions in CountSketch [49.57951567374372]
  We consider sketching algorithms which first compress data by multiplication with a random sketch matrix, and then apply the sketch to quickly solve an optimization problem. In this work, we propose the first learning-based algorithms that also optimize the locations of the non-zero entries.
  arXiv  Detail & Related papers  (2023-06-11T07:28:35Z)
• Classical and Quantum Iterative Optimization Algorithms Based on Matrix Legendre-Bregman Projections [1.5736899098702972]
  We consider Legendre-Bregman projections defined on the Hermitian matrix space and design iterative optimization algorithms based on them. We study both exact and approximate Bregman projection algorithms. In particular, our approximate iterative algorithm gives rise to the non-commutative versions of the generalized iterative scaling (GIS) algorithm for maximum entropy inference.
  arXiv  Detail & Related papers  (2022-09-28T15:59:08Z)
• First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems [88.58409977434269]
  We consider the problem of computing an equilibrium in a class of nonlinear generalized Nash equilibrium problems (NGNEPs) Our contribution is to provide two simple first-order algorithmic frameworks based on the quadratic penalty method and the augmented Lagrangian method. We provide nonasymptotic theoretical guarantees for these algorithms.
  arXiv  Detail & Related papers  (2022-04-07T00:11:05Z)
• Fast Projected Newton-like Method for Precision Matrix Estimation under Total Positivity [15.023842222803058]
  Current algorithms are designed using the block coordinate descent method or the proximal point algorithm. We propose a novel algorithm based on the two-metric projection method, incorporating a carefully designed search direction and variable partitioning scheme. Experimental results on synthetic and real-world datasets demonstrate that our proposed algorithm provides a significant improvement in computational efficiency compared to the state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-12-03T14:39:10Z)
• Quantum Algorithms for Prediction Based on Ridge Regression [0.7612218105739107]
  We propose a quantum algorithm based on ridge regression model, which get the optimal fitting parameters. The proposed algorithm has a wide range of application and the proposed algorithm can be used as a subroutine of other quantum algorithms.
  arXiv  Detail & Related papers  (2021-04-27T11:03:52Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices. We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
  arXiv  Detail & Related papers  (2020-11-12T16:29:45Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  This class of algorithms encompasses several randomized methods among the fastest solvers for least-squares problems. We focus on two classical embeddings, namely, Gaussian projections and subsampled Hadamard transforms. Our resulting algorithm yields the best complexity known for solving least-squares problems with no condition number dependence.
  arXiv  Detail & Related papers  (2020-02-21T17:45:32Z)
• 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.