2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$ Apr 11, 2012 at 6:29
  • $\begingroup$ "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). $\endgroup$ Apr 11, 2012 at 7:37
  • $\begingroup$ 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 $\endgroup$
    – Kostas
    Apr 11, 2012 at 15:03

1 Answer 1

2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.