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 $\mathcal{N}(\mathbf{A})$ an orthonormal basis of the null space 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 and $\mathbf{N} \in \mathcal{N}(\mathbf{A})$.

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}||_2$=0, $\forall \mathbf{x} \in \mathcal{C}^{(m-n) \times 1}$. 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}

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).

Questions:

1) An issue that I have with the above formulation has to do with the uniqueness of $\mathcal{N}(\mathbf{A})$ as obtained from the SVD. I guess that it is unique up to permutations and linear combinations of the columns (characteristic inherited from the SVD properties). So, T seems not to be well-defined. Is there a way to remove this ambiguity?

2) 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