Majorization for Changes in Angles Between Subspaces, Ritz Values, and Graph Laplacian Spectra

Abstract

Many inequality relations between real vector quantities can be succinctly expressed as "weak (sub)majorization" relations. We explain these ideas and apply them in several areas: angles between subspaces, Ritz values, and graph Laplacian spectra, which we show are all surprisingly related... An application of our Ritz values weak majorization result for Laplacian graph spectra comparison is suggested, based on the possibility to interpret eigenvalues of the edge Laplacian of a given graph as Ritz values of the edge Laplacian of the complete graph. We prove that ${\sum }_k|\lambda 1_k-\lambda 2_k|\le nl,$ where $\lambda 1_k$ and $\lambda 2_k$ are all ordered elements of the Laplacian spectra of two graphs with the same $n$ vertices and with $l$ equal to the number of differing edges.

Accepted to SIMAX

Cited by in corpus (11)

• A wildland fire model with data assimilation
• Angles between subspaces and their tangents
• Rayleigh-Ritz majorization error bounds with applications to FEM
• Angles Between Infinite Dimensional Subspaces with Applications to the Rayleigh-Ritz and Alternating Projectors Methods
• Bounds on changes in Ritz values for a perturbed invariant subspace of a Hermitian matrix
• Weakly Convex Optimization over Stiefel Manifold Using Riemannian Subgradient-Type Methods
• Non-Parametric Estimation of Manifolds from Noisy Data
• Simulating sticky particles: A Monte Carlo method to sample a stratification
• Rayleigh-Ritz majorization error bounds of the mixed type
• Majorization bounds for Ritz values of self-adjoint matrices
• Counting Collisions in an $N$-Billiard System Using Angles Between Collision Subspaces