Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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