Null Space Perturbations

Question

Hi,

I face a problem some time now (not a homework problem) and I believe it is related to matrix perturbations and how the null space behaves in these cases.

The distilled version of the problem is the following:

Let $\mathbf{A} \in \mathbb{C}^{n \times m}$ where $n < m$. Define as $\mathbf{N}$ an orthonormal basis of the null space $\mathcal{N}(\mathbf{A})$ of the matrix $\mathbf{A}$ obtained from the singular value decomposition. Let $\mathbf{\tilde{A}}$ a perturbed version of $\mathbf{A}$. It has the same dimensions as $\mathbf{A}$. I am interested in what happens to the quantity:

$T = \frac{||\mathbf{\tilde{A}} \cdot \mathbf{N}||}{||\mathbf{\tilde{A}}||}$

where $|| \cdot ||$ is the spectral norm.

The intuition behind this quantity is:

Assume I have a linear system $\mathbf{y} = \mathbf{A} \cdot \mathbf{x}$. I am allowed to use a matrix $\mathbf{N}$ such that I perform the operation $\mathbf{y} = \mathbf{A} \cdot \mathbf{N} \cdot \mathbf{x}$ and achieve $||\mathbf{A}\cdot\mathbf{N}\cdot \mathbf{x}||$=0, $\forall \mathbf{x} \in \mathcal{C}^{(m-n) \times 1}$. (note that the last $||\cdot||$ means euclidean norm). Then, I should use $\mathbf{N} \in \mathcal{N}(A)$. ($\mathbf{y}=0$ always)

Yet, there is an uncertainty about the actual matrix of the system. I know $\mathbf{A}$ but the actual matrix is $\mathbf{\tilde{A}}$. How much do I "gain" by using a matrix $\mathbf{N} \in \mathcal{N}(A)$ and not just ignore that I have this matrix? Specifically:

\begin{align} T &= \frac{\max\limits_{\mathbf{x}:|| \mathbf{x}||=1}||\mathbf{\tilde{A}} \cdot \mathbf{N} \cdot \mathbf{x}||}{\max\limits_{\mathbf{x}:||\mathbf{x}||=1}||\mathbf{\tilde{A}} \cdot \mathbf{x}||} \end{align}

where the notation $||\cdot||$ on a matrix means spectral norm and on a vector means euclidean norm. This is the same as:

$T = \frac{||\mathbf{\tilde{A}} \cdot \mathbf{N}||}{||\mathbf{\tilde{A}}||}$

If $\mathbf{N}$ is still close to the null space of $\mathbf{\tilde{A}}$, then T will be small, otherwise it will be big (always less or equal to 1).

I am interested on the rate of convergence, or on a bound of the quantity T as a function of the perturbation. I guess that specific assumptions need to be made about the perturbation, but do any assumptions you want. For example, if we have a perturbation of $\mathbf{\tilde{A}} = \mathbf{A} + \epsilon \mathbf{I}$, then is is possible to bound T, as a function of $\epsilon$? This is just an example. Maybe something can be said when we assume another perturbation.

Any comment on this problem or a reference on similar problems would be really appreciated!!

Thank you very much for your time,

Best,

Alex

EDIT: The ambiguity problem has been solved. If $\mathbf{N}$ is an orthornormal basis $ \mathcal{N}(A)$ (i.e. $\mathbf{N}'*\mathbf{N}=\mathbf{I}$) then T is uniquely defined.

Answer 1

What follows is just a trivial manipulation, but I do not think you can get better bounds than that for a generic perturbation.

If you write $\tilde{A}=A+\Delta A$, then you get $\tilde AN=(\Delta A )N$, which has norm smaller than $\left\Vert\Delta A \right\Vert$. Your denominator is essentially $\left\Vert A \right \Vert$, for small perturbations, so you can drop the tilde. This gives you $T \leq \lVert \Delta A \rVert / \lVert A \rVert$ (up to first order in $\lVert \Delta A \rVert$, otherwise you have to take into account the additional term in the denominator depending on how large your perturbation can be. If $\lVert \Delta A \rVert$ is allowed to be large, clearly $T$ can get arbitrarily close to 1).