5
$\begingroup$

Given a row-stochastic matrix $M$ with singular values $\sigma_{1} \geq \cdots \geq \sigma_{n}$, I am looking for an upper bound on the expression

$$\min_{\alpha} \left\| M- \frac{\alpha}{n}J_{n} \right\|_{2}$$

where $J_{n}$ is the matrix with all ones.

It is not hard to see that if $M$ is doubly stochastic, the above expression is exactly $\sigma_{2}$ (as the singular vector of the largest singular values is the vector of all ones), for $\alpha =1$. Can you find a similar bound when $M$ is only row stochastic?

Thank you.

Edit: Suppose we take $a, b$ to be the left and right singular vectors corresponding to the largest singular value $\sigma_{1}$. Then,

$$\| M- \frac{\alpha}{n}J_{n}-\sigma_{1}ab^T+\sigma_{1}ab^T \|_{2} < \sigma_{2}+\sigma_{1}\left(\sqrt{1-\frac{\left< a,e\right> ^{2}\left< b,e\right> ^{2}}{N^{2}}}\right)$$

for

$$\alpha = \frac{\sigma_{1}\left< a,e\right> ^{2}\left< b,e\right>^{2}}{N^{2}}$$

For a doubly stochastic matrix, this bound is tight (as the first singular vectors are $\frac{1}{\sqrt{N}}e$). What can we say, for example, of $\left< a,e\right> \left< b,e\right>$, when $\sigma_{1}$ is not 1, but very close to it?

$\endgroup$
2
  • $\begingroup$ A minor observation, $\alpha=1$ is the minimizer for the Frobenius norm; you are probably looking at the operator norm. $\endgroup$
    – Suvrit
    Mar 22, 2013 at 19:33
  • $\begingroup$ Indeed, I am looking for the l2 norm. Thanks. $\endgroup$
    – Daniel86
    Mar 22, 2013 at 19:57

1 Answer 1

3
$\begingroup$

Some experimentation led me to the following results:

  1. $\alpha=1$ yields the minimum value even for the operator-2 norm (certainly provable directly too)
  2. $\|M-ee^T/n\|_2$ can be larger than $\sigma_2 + \cdots + \sigma_n$
  3. $\|M-2ee^T/n\|_2 = \sigma_1(M)$ (obviously, since $M$ is rs)

So the only reasonable bound is: $\|M-ee^T/n\|_2 \le c_n\sigma_1(M)$, where the constant $c_n$ depends on the dimensionality $n$. As of now, I am using $c_n=1$, but have not paid much thought to what the best constant would be (need to dig up some singular value inequalities for that).

Here is an example matrix for which $\|M-ee^T/n\|_2 \ge 0.9\sigma_1(M)$.

\begin{equation*} M = \frac{1}{1000}\begin{pmatrix} 10 & 24 & 966\\\\ 410 & 576 & 14\\\\ 529 & 362 & 109 \end{pmatrix}. \end{equation*}

$\endgroup$
3
  • $\begingroup$ Thank you for your insights. I also figured that $\alpha = 1$ yields the minimum value also for the spectral norm. However, can you think of a matrix with a large gap between $\sigma_{1}$ and $\sigma_{2}$ (let's say, depends on $n$) for which this expression is as large as a factor of $\sigma_{1}$? I have some (maybe wrong) intuition that it decreases with the second singular values (maybe depends on $n$). $\endgroup$
    – Daniel86
    Mar 24, 2013 at 20:57
  • $\begingroup$ Try the Pascal matrix (for which the bounds should be derivable, or at least estimable analytically) --- (this matrix can be generated in Matlab using the command 'pascal'); for this matrix, it seems that $\|M-ee^T/n\|_2 > 0.5\sigma_1$, and that the gap between $\sigma_1$ and $\sigma_2$ is fairly large (of course, I scaled the matrix to be row-stochastic before testing the above claims) $\endgroup$
    – Suvrit
    Mar 25, 2013 at 1:47
  • $\begingroup$ @S. Sra , your comments lead me to think that it depends on how close $\sigma_{1}$ is to 1, see my edit above. What do you think? $\endgroup$
    – Daniel86
    Apr 1, 2013 at 11:32

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.