Skip to main content
MathOverflow

Return to Answer

overhauled answer.
Source Link
Suvrit
Suvrit
  • 28.6k
  • 7
  • 82
  • 150

Revised to include details of general $\alpha$

While not a complete answer, here are some ideas that may be of interest.

In particular, some experimentation shows that $K_L^TK_L$ hasDefine $1/2^{L-1}$ on its diagonal$\theta = (1+\alpha)^2$.

To ease notation, andI'll write $1/2^{L}$ and$K_L$ to mean $1/2^{L-1}$ spread out through the matrix in$K_L(\alpha)$. Some experimentation reveals a fairly regular waynice pattern satisfied by (one can count nicely)$M_L := K_L^TK_L$. It seems that, for example, in each column of this productIn particular, the entrywe see that $1/2^{L-2}$ occurs a maximum$M_L$ is comprised of two numbers, $2^{L-1}-1$ times$\frac{\theta}{2^L}$ and a minimum of $2^{L-2}$ times. Now we can use the Perron$\frac{2\theta}{2^L}$, which occur in a well-Frobeniusstructured pattern. We seek to bound on the largest eigenvaluePerron-Frobenius root, say $\rho$ of thisthe nonnegative matrix $M_L$. For this, first computeLooking at the largestpattern of $M_L$ we see that the smallest possible column sum of $M_L$ happens when $\theta$ arises $2^{L-1}-1$ times and $2\theta$ arises once. Thus, which yieldswe see that $\rho \le 2^{L-2}\times \frac{1}{2^{L}} +(2^{L-1}-2^{L-2})\times \frac{1}{2^{L-1}} = 3/4$.\begin{equation*} \rho \ge (2^{L-1}-1)\frac{\theta}{2^L} + \frac{2\theta}{2^L} = \theta\left(\frac{1}{2}+\frac{1}{2^L}\right). \end{equation*}

WhileSimilarly, by looking at the smallest possible column sumpattern, we see that the largest row-sum happens when $\theta$ appears $2^{L-2}$ times and $2\theta$ appears $2^{L-1}-2^{L-2}$ times (noting that $M_L$ is $(2^{L-1}-1)\frac{1}{2^{L-2}} + \frac{1}{2^L} = \frac{1}{2}-\frac{3}{2^L} \ge \rho$ of size $2^{L-1} \times 2^{L-1}$). Thus, we see that \begin{equation*} \rho \le 2^{L-2}\frac{\theta}{2^L} + (2^{L-1}-2^{L-2}) \frac{2\theta}{2^L} = \frac{3}{4}\theta. \end{equation*}

ThusExample, when $\sqrt{\frac{1}{2}-\frac{3}{2^L}} \le \sigma_1(K_L(0)) \le \sqrt{\frac{3}{4}}$$\alpha=0$, so that as then $L\to \infty$$\theta=1$, and the lowerupper bound becomes the boringon $1/2$. Numerically$\sigma_1(K_L) = \sqrt{\rho} \le \sqrt{3/4}$, it seems that the $\sigma_1(K_L(0))$ goes rather towards $\sqrt{3/4}$otherwise, which can probably be characterized more precisely.we get \begin{equation*} \sigma_1(K_L) \le (1+\alpha)\sqrt{\frac{3}{4} }. \end{equation*}

The matrices $K_L(\alpha)^TK_L(\alpha)$ exhibit the same patternAs I noted previously, and one can after some labor obtaina more careful analysis is needed to refine these bounds such as and to characterize how the above onelimiting value is achieved (perhaps we can leverage $K_L$ being a column stochastic matrix?), but this bound is numerically not too bad. On the experimental sideFor example, a quick numerical experiment shows that $\sigma_1(K_L(0)) \to 0.8254....$ very rapidly (already for $K_7$, the first 4 digits match).

While not a complete answer, here are some ideas that may be of interest.

In particular, some experimentation shows that $K_L^TK_L$ has $1/2^{L-1}$ on its diagonal, and $1/2^{L}$ and $1/2^{L-1}$ spread out through the matrix in a fairly regular way (one can count nicely). It seems that, for example, in each column of this product, the entry $1/2^{L-2}$ occurs a maximum of $2^{L-1}-1$ times and a minimum of $2^{L-2}$ times. Now we can use the Perron-Frobenius bound on the largest eigenvalue, say $\rho$ of this matrix. For this, first compute the largest possible column sum, which yields $\rho \le 2^{L-2}\times \frac{1}{2^{L}} +(2^{L-1}-2^{L-2})\times \frac{1}{2^{L-1}} = 3/4$.

While the smallest possible column sum is $(2^{L-1}-1)\frac{1}{2^{L-2}} + \frac{1}{2^L} = \frac{1}{2}-\frac{3}{2^L} \ge \rho$.

Thus, $\sqrt{\frac{1}{2}-\frac{3}{2^L}} \le \sigma_1(K_L(0)) \le \sqrt{\frac{3}{4}}$, so that as $L\to \infty$, the lower bound becomes the boring $1/2$. Numerically, it seems that the $\sigma_1(K_L(0))$ goes rather towards $\sqrt{3/4}$, which can probably be characterized more precisely.

The matrices $K_L(\alpha)^TK_L(\alpha)$ exhibit the same pattern, and one can after some labor obtain bounds such as the above one. On the experimental side, a quick numerical experiment shows that $\sigma_1(K_L(0)) \to 0.8254....$ very rapidly (already for $K_7$, the first 4 digits match).

Revised to include details of general $\alpha$

While not a complete answer, here are some ideas that may be of interest.

Define $\theta = (1+\alpha)^2$.

To ease notation, I'll write $K_L$ to mean $K_L(\alpha)$. Some experimentation reveals a nice pattern satisfied by $M_L := K_L^TK_L$. In particular, we see that $M_L$ is comprised of two numbers, $\frac{\theta}{2^L}$ and $\frac{2\theta}{2^L}$, which occur in a well-structured pattern. We seek to bound the Perron-Frobenius root, say $\rho$ of the nonnegative matrix $M_L$. Looking at the pattern of $M_L$ we see that the smallest possible column sum of $M_L$ happens when $\theta$ arises $2^{L-1}-1$ times and $2\theta$ arises once. Thus, we see that \begin{equation*} \rho \ge (2^{L-1}-1)\frac{\theta}{2^L} + \frac{2\theta}{2^L} = \theta\left(\frac{1}{2}+\frac{1}{2^L}\right). \end{equation*}

Similarly, by looking at the pattern, we see that the largest row-sum happens when $\theta$ appears $2^{L-2}$ times and $2\theta$ appears $2^{L-1}-2^{L-2}$ times (noting that $M_L$ is of size $2^{L-1} \times 2^{L-1}$). Thus, we see that \begin{equation*} \rho \le 2^{L-2}\frac{\theta}{2^L} + (2^{L-1}-2^{L-2}) \frac{2\theta}{2^L} = \frac{3}{4}\theta. \end{equation*}

Example, when $\alpha=0$, then $\theta=1$, and the upper bound on $\sigma_1(K_L) = \sqrt{\rho} \le \sqrt{3/4}$, otherwise, we get \begin{equation*} \sigma_1(K_L) \le (1+\alpha)\sqrt{\frac{3}{4} }. \end{equation*}

As I noted previously, a more careful analysis is needed to refine these bounds and to characterize how the limiting value is achieved (perhaps we can leverage $K_L$ being a column stochastic matrix?), but this bound is numerically not too bad. For example, a quick numerical experiment shows that $\sigma_1(K_L(0)) \to 0.8254....$ very rapidly (already for $K_7$, the first 4 digits match).

added one more sentence
Source Link
Suvrit
Suvrit
  • 28.6k
  • 7
  • 82
  • 150

While not a complete answer, here are some ideas that may be of interest.

In particular, some experimentation shows that $K_L^TK_L$ has $1/2^{L-1}$ on its diagonal, and $1/2^{L}$ and $1/2^{L-1}$ spread out through the matrix in a fairly regular way (one can count nicely). It seems that, for example, in each column of this product, the entry $1/2^{L-2}$ occurs a maximum of $2^{L-1}-1$ times and a minimum of $2^{L-2}$ times. Now we can use the Perron-Frobenius bound on the largest eigenvalue, say $\rho$ of this matrix. For this, first compute the largest possible column sum, which yields $\rho \le 2^{L-2}\times \frac{1}{2^{L}} +(2^{L-1}-2^{L-2})\times \frac{1}{2^{L-1}} = 3/4$.

While the smallest possible column sum is $(2^{L-1}-1)\frac{1}{2^{L-2}} + \frac{1}{2^L} = \frac{1}{2}-\frac{3}{2^L} \ge \rho$.

Thus, $\sqrt{\frac{1}{2}-\frac{3}{2^L}} \le \sigma_1(K_L(0)) \le \sqrt{\frac{3}{4}}$, so that as $L\to \infty$, the lower bound becomes the boring $1/2$. Numerically, it seems that the $\sigma_1(K_L(0))$ goes rather towards $\sqrt{3/4}$, which can probably be characterized more precisely.

The matrices $K_L(\alpha)^TK_L(\alpha)$ exhibit the same pattern, and one can after some labor obtain bounds such as the above one. On the experimental side, a quick numerical experiment shows that $\sigma_1(K_L(0)) \to 0.8254....$ very rapidly (already for $K_7$, the first 4 digits match).

While not a complete answer, here are some ideas that may be of interest.

In particular, some experimentation shows that $K_L^TK_L$ has $1/2^{L-1}$ on its diagonal, and $1/2^{L}$ and $1/2^{L-1}$ spread out through the matrix in a fairly regular way (one can count nicely). It seems that, for example, in each column of this product, the entry $1/2^{L-2}$ occurs a maximum of $2^{L-1}-1$ times and a minimum of $2^{L-2}$ times. Now we can use the Perron-Frobenius bound on the largest eigenvalue, say $\rho$ of this matrix. For this, first compute the largest possible column sum, which yields $\rho \le 2^{L-2}\times \frac{1}{2^{L}} +(2^{L-1}-2^{L-2})\times \frac{1}{2^{L-1}} = 3/4$.

While the smallest possible column sum is $(2^{L-1}-1)\frac{1}{2^{L-2}} + \frac{1}{2^L} = \frac{1}{2}-\frac{3}{2^L} \ge \rho$.

Thus, $\sqrt{\frac{1}{2}-\frac{3}{2^L}} \le \sigma_1(K_L(0)) \le \sqrt{\frac{3}{4}}$, so that as $L\to \infty$, the lower bound becomes the boring $1/2$. Numerically, it seems that the $\sigma_1(K_L(0))$ goes rather towards $\sqrt{3/4}$, which can probably be characterized more precisely.

While not a complete answer, here are some ideas that may be of interest.

In particular, some experimentation shows that $K_L^TK_L$ has $1/2^{L-1}$ on its diagonal, and $1/2^{L}$ and $1/2^{L-1}$ spread out through the matrix in a fairly regular way (one can count nicely). It seems that, for example, in each column of this product, the entry $1/2^{L-2}$ occurs a maximum of $2^{L-1}-1$ times and a minimum of $2^{L-2}$ times. Now we can use the Perron-Frobenius bound on the largest eigenvalue, say $\rho$ of this matrix. For this, first compute the largest possible column sum, which yields $\rho \le 2^{L-2}\times \frac{1}{2^{L}} +(2^{L-1}-2^{L-2})\times \frac{1}{2^{L-1}} = 3/4$.

While the smallest possible column sum is $(2^{L-1}-1)\frac{1}{2^{L-2}} + \frac{1}{2^L} = \frac{1}{2}-\frac{3}{2^L} \ge \rho$.

Thus, $\sqrt{\frac{1}{2}-\frac{3}{2^L}} \le \sigma_1(K_L(0)) \le \sqrt{\frac{3}{4}}$, so that as $L\to \infty$, the lower bound becomes the boring $1/2$. Numerically, it seems that the $\sigma_1(K_L(0))$ goes rather towards $\sqrt{3/4}$, which can probably be characterized more precisely.

The matrices $K_L(\alpha)^TK_L(\alpha)$ exhibit the same pattern, and one can after some labor obtain bounds such as the above one. On the experimental side, a quick numerical experiment shows that $\sigma_1(K_L(0)) \to 0.8254....$ very rapidly (already for $K_7$, the first 4 digits match).

Source Link
Suvrit
Suvrit
  • 28.6k
  • 7
  • 82
  • 150

While not a complete answer, here are some ideas that may be of interest.

In particular, some experimentation shows that $K_L^TK_L$ has $1/2^{L-1}$ on its diagonal, and $1/2^{L}$ and $1/2^{L-1}$ spread out through the matrix in a fairly regular way (one can count nicely). It seems that, for example, in each column of this product, the entry $1/2^{L-2}$ occurs a maximum of $2^{L-1}-1$ times and a minimum of $2^{L-2}$ times. Now we can use the Perron-Frobenius bound on the largest eigenvalue, say $\rho$ of this matrix. For this, first compute the largest possible column sum, which yields $\rho \le 2^{L-2}\times \frac{1}{2^{L}} +(2^{L-1}-2^{L-2})\times \frac{1}{2^{L-1}} = 3/4$.

While the smallest possible column sum is $(2^{L-1}-1)\frac{1}{2^{L-2}} + \frac{1}{2^L} = \frac{1}{2}-\frac{3}{2^L} \ge \rho$.

Thus, $\sqrt{\frac{1}{2}-\frac{3}{2^L}} \le \sigma_1(K_L(0)) \le \sqrt{\frac{3}{4}}$, so that as $L\to \infty$, the lower bound becomes the boring $1/2$. Numerically, it seems that the $\sigma_1(K_L(0))$ goes rather towards $\sqrt{3/4}$, which can probably be characterized more precisely.