4

if $X$ is a matrix with unitary columns ( each column has unit norm ), are there lower and upper bounds on the minimum and maximum singular values of $X$?

I could prove a lower bound for $\Sigma_{min}$ and $\Sigma_{max}$ i.e. $\Sigma_{min} \geq 0$ and $\Sigma_{max} \geq 1$, respectively.

Do upper bounds exist for the same?

Thanks in advance.

Karthik Upadhya
  • 734
  • 7
  • 15

2 Answers2

2

By unitary I assume you mean that the colums have unit norm. This in turn implies that the entries of the matrix $X$ are bounded in absolute value by $1$, i.e. $|x_{i,j}|\leq 1$. Since the largest singular value coincides with the matrix norm (if I am not mistaken) one can do the following estimate ($d$ is the dimension) $$ \lVert Xv \rVert^2 = \sum_i \left( \sum_j x_{i,j} v_j \right)^2 \leq \sum_i \left( \sum_j |x_{i,j}| |v_j| \right)^2 \leq \sum_i \lVert v \rVert_1^2 = d\lVert v \rVert_1^2 $$ Since all norms are equivalent in finite dimensions we can estimate $\lVert v \rVert_1 \leq C_d \lVert v \rVert_2$. Therefore we have found a bound for the operator norm and further also for the maximal singular value of $X$.

Hope this helps...

Chris
  • 398
  • While true, the bound obtained in this way has a small flaw that it overestimates $|X|$ for any $X$ with normalized columns (except when $d=1$). Since $C_d=\sqrt{d}$, it shows that $|X|\leq d$, while the attainable bound can be made equal to $\sqrt{d}$. – Algebraic Pavel Sep 17 '14 at 21:00
2

If $X$ is $m\times n$, the best upper bound for $\Sigma_{\max}=\|X\|_2$ you can get is $\sqrt{n}$. The fact that this is an upper bound can be shown, e.g., by using the fact that $\|X\|_2^2\leq \rho(X^*X)\leq\mathrm{trace}(X^*X)=n$. The bound is attained for a matrix $X=[x,x,\ldots,x]$, where $\|x\|_2=1$.

No reasonable upper bound for the minimal singular value $\Sigma_{\min}$ can be obtained except the simple one $\Sigma_{\min}\leq 1$. Any $\Sigma_{\min}$ between zero and one can be obtained by considering $X=[x,y]$, where $\|x\|_2=\|y\|_2=1$, and changing the "angle" between $x$ and $y$ (zero is attained when $x=y$ and one is attained when $x$ and $y$ are orthogonal).

Algebraic Pavel
  • 22,928