# Null Space Perturbations

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.

-
Since matrix multiplication is continuous, $$\|\tilde{A} \mathcal{N}(A) \| \to 0$$ as $\tilde{A} \to A$. Taking the norm is also continuous, so $$\|\tilde{A}\| \to \|A\|.$$ Together, this entails that $T \to 0$ as $\tilde{A} \to A$. I imagine that you want something more specific than this - maybe something about the rate of convergence? Could you clarify? – Aaron Tikuisis Apr 11 '12 at 6:29
"The intuition behind this quantity is: Assume I have a linear system (y=A⋅x). I am allowed to use a precoding matrix and actually pass through the system N⋅x such that the power of the output of the system is zero. Then, I should use as a precoding matrix a matrix in the null space of A." Can you please rewrite this part using more universal terms? I have no idea what "precoding matrix", "the power of the output", and "pass through the system" mean --- they may make sense in your application, but they are not widely understood (at least if "widely" has to include me :p). – Federico Poloni Apr 11 '12 at 7:37
Hi, Thank you for your comments. I have reviewed the statement of the problem and I think it is more clear now. Also, yes I am interested on bounds and rate of convergence of this quantity. Best, Alex – Kostas Apr 11 '12 at 15:03

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