The Index of Invariance and its Implications for a Parameterized Least Squares Problem

Abstract

We study the problem $x_{b,\omega }:={\text{arg min}}_{x\in \mathcal{S}}\Vert (A+\omega I{)}^{-1/2}(b-Ax){\Vert }_2$, with $A=A^{\ast }$, for a subspace $\mathcal{S}$ of ${\mathbb{F}}^n$ ($\mathbb{F}=\mathbb{R}$ or $\mathbb{C}$), and $\omega >-{\lambda }_{min}(A)$. We show that there exists a subspace $\mathcal{Y}$ of ${\mathbb{F}}^n$, independent of $b$, such that $\{x_{b,\omega }-x_{b,\mu }\mid \omega ,\mu >-{\lambda }_{min}(A)\}\subseteq \mathcal{Y}$, where $\dim (\mathcal{Y})\le \dim (\mathcal{S}+A\mathcal{S})-\dim (\mathcal{S})={\mathbf{Ind}}_A(\mathcal{S})$, a quantity which we call the index of invariance of $\mathcal{S}$ with respect to $A$. In particular if $\mathcal{S}$ is a Krylov subspace, this implies the low dimensionality result of Hallman & Gu (2018). The problem is also such that when $A$ is positive and $\mathcal{S}$ is a Krylov subspace, it reduces to CG for $\omega =0$ and to MINRES for $\omega \to \infty$. We study several properties of ${\mathbf{Ind}}_A(\mathcal{S})$ in relation to $A$ and $\mathcal{S}$. We show that the dimension of the affine subspace ${\mathcal{X}}_b$ containing the solutions $x_{b,\omega }$ can be smaller than ${\mathbf{Ind}}_A(\mathcal{S})$ for all $b$. However, we also exhibit some sufficient conditions on $A$ and $\mathcal{S}$, under which $\mathcal{X}:=\text{Span}\{x_{b,\omega }-x_{b,\mu }\mid b\in {\mathbb{F}}^n,\omega ,\mu >-{\lambda }_{min}(A)\}$ has dimension equal to ${\mathbf{Ind}}_A(\mathcal{S})$. We then study the injectivity of the map $\omega \mapsto x_{b,\omega }$, leading us to a proof of the convexity result from Hallman & Gu (2018). We finish by showing that sets such as $M(\mathcal{S},{\mathcal{S}}^{\prime })=\{A\in {\mathbb{F}}^{n\times n}\mid \mathcal{S}+A\mathcal{S}={\mathcal{S}}^{\prime }\}$, for nested subspaces $\mathcal{S}\subseteq {\mathcal{S}}^{\prime }\subseteq {\mathbb{F}}^n$, form smooth real manifolds, and explore some topological relationships between them.