论文标题
随机Toeplitz矩阵：高随机依赖性下的条件号
Random Toeplitz Matrices: The Condition Number under High Stochastic Dependence
论文作者
论文摘要
在本文中，我们研究了随机托管基质的条件数。由于toeplitz矩阵是对角线常数矩阵，因此其行或列不能随机独立。当随机矩阵的所有条目随机独立时，这种情况不允许我们使用经典策略来分析其最小值。使用循环嵌入，我们可以打破Toeplitz基质结构的随机依赖性，并减少问题，以分析随机循环矩阵的极端奇异值。在我们的结果中，我们显示了在随机条目的力矩生成函数的存在下的非对称随机循环矩阵的条件数为$κ\ left（\ Mathcal {c} _n \ right）= \ mbox {\ mbox {o} {o} {o} \ left（\ log n \ right）^{1/2} \ right）$带有概率$ 1- \ mbox {o} \ left（（（（\ varepsilon^2 + \ varepsilon）n^{ - 2ρ} { - 2ρ} + n^ + n^ + n^{ - 1/2 + \\ scridsStyle {op} $} $} $} $} $} $ρ\ in（0,1/4）$。此外，如果随机条目仅具有第二刻，我们有$κ\ left（\ Mathcal {c} _n \ right）= \ mbox {o} \ left（\ frac {1} {\ varepsilon} $ 1- \ mbox {o} \ left（（\ varepsilon^2 + \ varepsilon）n^{ - 2ρ} + \ left（\ log n \ right）^{ - 1/2} \ right）$。对于随机（非对称或对称）toeplitz矩阵$ \ MATHCAL {t} _n $的条件数，我们建立$κ\ left（\ Mathcal {t} _n \ right） \ left（σ_ {\ min} \ left（c_ {2n} \右）σ_{\ min} \ left（s_n \ right）\ right）^{ - 1} $，其中$σ_{\ min}（a min}（a）$是Matrix $ a $ a $ a $ a $的最小单数。矩阵$ c_ {2n} $是一个随机循环矩阵，$ s_n：= f^*_ {2，n} d_ {1，n}^{ - 1} f _ {2，n} + f^*_ {4，n} d^_ {4，n} $ f_ {2，n}，f_ {4，n} $是确定性矩阵，$ d_ {1，n}，d_ {2，n} $是随机的对角线矩阵。我们连接$ s_n $的条件良好。
In this paper, we study the condition number of a random Toeplitz matrix. Since a Toeplitz matrix is a diagonal constant matrix, its rows or columns cannot be stochastically independent. This situation does not permit us to use the classic strategy to analyze its minimum singular value when all the entries of a random matrix are stochastically independent. Using a circulant embedding, we can break the stochastic dependence of the structure of the Toeplitz matrix and reduce the problem to analyze the extreme singular values of a random circulant matrix. Among our results, we show the condition number of non--symmetric random circulant matrix of dimension $n$ under the existence of moment generating function of the random entries is $κ\left(\mathcal{C}_n\right) = \mbox{O}\left( \frac{1}{\varepsilon} n^{ρ+1/2} \left(\log n\right)^{1/2} \right)$ with probability $1-\mbox{O}\left((\varepsilon^2 + \varepsilon) n^{-2ρ} + n^{-1/2+\scriptstyle{o}(1)}\right)$ for any $\varepsilon >0$, $ρ\in(0,1/4)$. Moreover, if the random entries only have the second moment, we have $κ\left(\mathcal{C}_n\right) = \mbox{O}\left( \frac{1}{\varepsilon} n^{ρ+1/2} \log n\right)$ with probability $1-\mbox{O}\left((\varepsilon^2 + \varepsilon) n^{-2ρ} + \left(\log n\right)^{-1/2}\right)$. For the condition number of a random (non--symmetric or symmetric) Toeplitz matrix $\mathcal{T}_n$ we establish $κ\left(\mathcal{T}_n\right) \leq κ\left(\mathcal{C}_{2n}\right) \left(σ_{\min}\left( C_{2n} \right)σ_{\min}\left( S_n \right)\right)^{-1}$, where $σ_{\min}(A)$ is the minimum singular value of the matrix $A$. The matrix $C_{2n}$ is a random circulant matrix and $S_n:=F^*_{2,n} D_{1,n}^{-1}F_{2,n} + F^*_{4,n} D^{-1}_2 F_{4,n}$, where $F_{2,n},F_{4,n}$ are deterministic matrices and $D_{1,n}, D_{2,n}$ are random diagonal matrices. We conjeture $S_n$ is well conditioned.
