3
$\begingroup$

Given SPD matrix $$A \in \mathbb{R}^{N \times N} $$ and positive diagonal matrix $$D \in \mathbb{R}^{N\times N}.$$ What is then spectrum of the product $$D^TAD.$$ Is there a closed-form relationship between spectra of $A, D$ and that of the product? Or at least can we find bounds of it?

E.g., one can see that if $D = \alpha I$ then $cond(A) = cond(D^TAD)$ for any $\alpha > 0$.

UPDATE: In practice I observe that for arbitrary positive $D$ the $cond(A) < cond(D^TAD)$. However, I can not explain or understand it. Any clues are appreciated.

UPDATE: The following MATLAB script generates $k$ random matrices $A$ and $D$ and then $i$ times decreases the smallest diagonal element of $D$ by factor $r < 1$, calculating at each iteration condition number of the product $D^TAD$ with updated $D$:

sz = 100;

v = [];
cw = []; ch = [];

r = 0.75;

for k=1:100

    A = 4 + 1.*randn(sz);
    A = A'*A;
    W = diag(4 + 1.*randn(sz,1));

    cw(1) = cond(W);
    ch(1) = cond(W'*A*W);

    [c, j] = min(diag(W));
    for i=1:25
        W(j,j) = W(j,j) * r;
        cw(i+1) = cond(W);
        ch(i+1) = cond(W'*A*W);
    end

    v(:,k) = (ch(2:end)./ch(1:end-1))';
end
plot(v);
axis([1 i 1 1/r^2]);

If I plot then ratios of condition numbers between iterations it approaches $1/r^2$. E.g., for $r = 0.75$:

And it is never larger than $1/r^2$. It tells that perhaps there should be bound for condition number of the product $D^TAD$ or we can even compute it knowing spectrum of $A$, but I can't figure it out. Can anyone help? Also, this effect seems to be independent of random generator and its parameters.

Improve this question
$\endgroup$
1
  • $\begingroup$ $cond(A)>cond(D^TAD)$ cannot hold in general but is due to your simulation recipe. If you write$A'=D^TAD$ and apply $D'=D^{-1}$ to $A'$ then you get back $A$, hence the opposite inequality. $\endgroup$ – Arnold Neumaier Jul 11 '12 at 17:44
3
$\begingroup$

There is no useful relationship. You can see this by looking at the $2\times 2$ case, where explicit formulas exist.

Edit; You can see from your plot that the worst cases in you sample curves are already very far from the typical cases. The absolutely worst would be even further off. Thus though one can perhaps prove optimal bounds (by writing down the optimatity conditions and analysing them), they would tell nothing useful about the typcal situation.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks Prof. Neumaier. Is this possible to get bounds on spectrum perturbations then? $\endgroup$ – Alexander Jul 11 '12 at 15:04
  • $\begingroup$ @Alexander: Bounds will be poor unless $D$ is close to a multiple the identity. $\endgroup$ – Arnold Neumaier Jul 11 '12 at 15:30
  • $\begingroup$ I updated my post concerning bounds. Does it tell anything? $\endgroup$ – Alexander Jul 11 '12 at 15:32
  • $\begingroup$ Yes, but not much. see my updated answer. $\endgroup$ – Arnold Neumaier Jul 11 '12 at 15:42
  • $\begingroup$ I see. Is it then possible under any conditions to say that condition number of the product $D^TAD$ is larger that that of $A$? I do observe this in practice, but can not formulate it or even just understand. $\endgroup$ – Alexander Jul 11 '12 at 15:49
1
$\begingroup$

If you are interested only in the $\kappa_2$ matrix condition number and not in the full spectrum, then your question is linked to linear system perturbation theory, where matrix $D$ is often used as a preconditioner.

A well known result is \begin{equation} \kappa_2(D_* A D_*) \leq N\min_{D \in \mathcal{D}_N} \kappa_2(DAD) \end{equation} where $D_* = \mathrm{diag}(a_{ii}^{-1/2})$, so that $(D_*AD_*)$ has unit diagonal, see corollary 7.6 (van der Sluis) in N. J. Higham, Accuracy and Stability of Numerical Algorithms (2nd ed.), SIAM 2002.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ @Alexander: the above result does not answer your question, but at least gives you an explicit recipe for constructing a $D$ that reduces the condition number. Further it is a hint for interpreting your results. In fact your experiments go exactly in the opposite direction: instead of balancing the diag terms of A, you choose a single diagonal element and you almost cancel it out. In fact after 25 iters the diag term get multiplied by $r^{50}\approx 5\times10^{-7}$. $\endgroup$ – Stefano M Jul 15 '12 at 9:24
0
$\begingroup$

Unless $A$ and $D$ are commutable, where the spectrum of the product is the product of spectra, there is no simple relationship.

Improve this answer
$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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