Block perturbation of symplectic matrices in Williamson's theorem

• URL: http://arxiv.org/abs/2307.01078v2
• Date: Thu, 17 Aug 2023 15:31:00 GMT
• Title: Block perturbation of symplectic matrices in Williamson's theorem
• Authors: Gajendra Babu and Hemant K. Mishra
• Abstract summary: We show that any symplectic matrix $tildeS$ diagonalizing $A+H$ in Williamson's theorem is of the form $tildeS=S Q+mathcalO(|H|)$. Our results hold even if $A$ has repeated symplectic eigenvalues.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Williamson's theorem states that for any $2n \times 2n$ real positive definite matrix $A$, there exists a $2n \times 2n$ real symplectic matrix $S$ such that $S^TAS=D \oplus D$, where $D$ is an $n\times n$ diagonal matrix with positive diagonal entries which are known as the symplectic eigenvalues of $A$. Let $H$ be any $2n \times 2n$ real symmetric matrix such that the perturbed matrix $A+H$ is also positive definite. In this paper, we show that any symplectic matrix $\tilde{S}$ diagonalizing $A+H$ in Williamson's theorem is of the form $\tilde{S}=S Q+\mathcal{O}(\|H\|)$, where $Q$ is a $2n \times 2n$ real symplectic as well as orthogonal matrix. Moreover, $Q$ is in $\textit{symplectic block diagonal}$ form with the block sizes given by twice the multiplicities of the symplectic eigenvalues of $A$. Consequently, we show that $\tilde{S}$ and $S$ can be chosen so that $\|\tilde{S}-S\|=\mathcal{O}(\|H\|)$. Our results hold even if $A$ has repeated symplectic eigenvalues. This generalizes the stability result of symplectic matrices for non-repeated symplectic eigenvalues given by Idel, Gaona, and Wolf [$\textit{Linear Algebra Appl., 525:45-58, 2017}$].

Related papers

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
  arXiv  Detail & Related papers  (2024-10-26T06:21:42Z)
• LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
  We show that for any $K$, there is a universal set" $U subset [n]$ of size independent of $n$, such that for any $Q$ and any row $i$, the large attention scores $A_i,j$ in row $i$ of $A$ all have $jin U$. We empirically show the benefits of our scheme for vision transformers, showing how to train new models that use our universal set while training as well.
  arXiv  Detail & Related papers  (2024-10-07T19:47:13Z)
• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  We study the problem of residual error estimation for matrix and vector norms using a linear sketch. We demonstrate that this gives a substantial advantage empirically, for roughly the same sketch size and accuracy as in previous work. We also show an $Omega(k2/pn1-2/p)$ lower bound for the sparse recovery problem, which is tight up to a $mathrmpoly(log n)$ factor.
  arXiv  Detail & Related papers  (2024-08-16T02:33:07Z)
• A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Time [7.613259578185218]
  We focus on giving a provable guarantee for the one-layer attention network objective function $L(X,Y). In a multi-layer LLM network, the matrix $B in mathbbRn times d2$ can be viewed as the output of a layer. We provide an iterative algorithm to train loss function $L(X,Y)$ up $epsilon$ that runs in $widetildeO( (cal T_mathrmmat(n,d) + d
  arXiv  Detail & Related papers  (2023-09-14T04:23:40Z)
• A General Algorithm for Solving Rank-one Matrix Sensing [15.543065204102714]
  The goal of matrix sensing is to recover a matrix $A_star in mathbbRn times n$, based on a sequence of measurements. In this paper, we relax that rank-$k$ assumption and solve a much more general matrix sensing problem.
  arXiv  Detail & Related papers  (2023-03-22T04:07:26Z)
• An Order Relation between Eigenvalues and Symplectic Eigenvalues of a Class of Infinite-Dimensional Operators [0.0]
  We prove an inequality between the eigenvalues and symplectic eigenvalues of a special class of infinite dimensional operators. The only possible accumulation point for the symplectic eigenvalues is $alpha$.
  arXiv  Detail & Related papers  (2022-12-07T19:00:32Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  We study iterative methods based on Krylov subspaces for low-rank approximation under any Schatten-$p$ norm. Our main result is an algorithm that uses only $tildeO(k/sqrtepsilon)$ matrix-vector products.
  arXiv  Detail & Related papers  (2022-02-10T16:10:41Z)
• Spectral properties of sample covariance matrices arising from random matrices with independent non identically distributed columns [50.053491972003656]
  It was previously shown that the functionals $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$. Here, we show that $|mathbb E[R(z)] - tilde R(z)|_F
  arXiv  Detail & Related papers  (2021-09-06T14:21:43Z)
• Maps preserving trace of products of matrices [1.4620086904601473]
  We prove the linearity and injectivity of two maps $phi_1$ and $phi$ on certain subsets of $M_n$. We apply it to characterize maps $phi_i:mathcalSto mathcalS$ ($i=1, ldots, m$) satisfyingoperatornametr (phi_m(A_m))=operatornametr (A_m)$$ in which $mathcalS$ is the set of $n$-by-$n
  arXiv  Detail & Related papers  (2021-03-22T01:39:04Z)
• The Average-Case Time Complexity of Certifying the Restricted Isometry Property [66.65353643599899]
  In compressed sensing, the restricted isometry property (RIP) on $M times N$ sensing matrices guarantees efficient reconstruction of sparse vectors. We investigate the exact average-case time complexity of certifying the RIP property for $Mtimes N$ matrices with i.i.d. $mathcalN(0,1/M)$ entries.
  arXiv  Detail & Related papers  (2020-05-22T16:55:01Z)

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.