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
- 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) - Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
We consider the problem of minimizing the number of matrix-vector queries needed for accurate trace estimation in the dynamic setting where our underlying matrix is changing slowly.
We provide a novel binary tree summation procedure that simultaneously estimates all $m$ traces up to $epsilon$ error with $delta$ failure probability.
Our lower bounds (1) give the first tight bounds for Hutchinson's estimator in the matrix-vector product model with Frobenius norm error even in the static setting, and (2) are the first unconditional lower bounds for dynamic trace estimation.
arXiv Detail & Related papers (2022-09-30T04:15:44Z) - 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) - Sparse sketches with small inversion bias [79.77110958547695]
Inversion bias arises when averaging estimates of quantities that depend on the inverse covariance.
We develop a framework for analyzing inversion bias, based on our proposed concept of an $(epsilon,delta)$-unbiased estimator for random matrices.
We show that when the sketching matrix $S$ is dense and has i.i.d. sub-gaussian entries, the estimator $(epsilon,delta)$-unbiased for $(Atop A)-1$ with a sketch of size $m=O(d+sqrt d/
arXiv Detail & Related papers (2020-11-21T01:33:15Z) - 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) - Average Case Column Subset Selection for Entrywise $\ell_1$-Norm Loss [76.02734481158458]
It is known that in the worst case, to obtain a good rank-$k$ approximation to a matrix, one needs an arbitrarily large $nOmega(1)$ number of columns.
We show that under certain minimal and realistic distributional settings, it is possible to obtain a $(k/epsilon)$-approximation with a nearly linear running time and poly$(k/epsilon)+O(klog n)$ columns.
This is the first algorithm of any kind for achieving a $(k/epsilon)$-approximation for entrywise
arXiv Detail & Related papers (2020-04-16T22:57:06Z)
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.