论文标题
估计最短路径协方差矩阵
Estimation of Shortest Path Covariance Matrices
论文作者
论文摘要
我们研究了估计分布$ \ Mathcal d $ the $ \ m mathbb {r}^d $的样本的样本复杂性，以估算\ mathbb {r}^{r}^{r}^{d \ times d} $的样本复杂性。特别是，我们专注于最短路径协方差矩阵，其中任何两个测量值之间的协方差取决于带有$ d $ nodes的基础图中的最短路径距离。此类矩阵将toeplitz和循环协方差矩阵概括，并广泛应用于信号处理应用中，其中两个测量值之间的协方差取决于它们在时间或空间上之间的（最短路径）距离。 我们专注于最小化矢量样本复杂性：从$ \ Mathcal {d} $绘制的样本数量和输入样本复杂性：每个样本中读取的条目数。进入样品复杂性对应于信号处理应用中的测量设备成本。 We give a very simple algorithm for estimating $\mathbfΣ$ up to spectral norm error $ε\left\|\mathbfΣ\right\|_2$ using just $O(\sqrt{D})$ entry sample complexity and $\tilde O(r^2/ε^2)$ vector sample complexity, where $D$ is the diameter of the underlying graph and $r \ le d $是$ \mathbfς$的等级。我们的方法是基于将稀疏统治者的广泛应用的概念扩展到图形设置中，以将稀疏的统治者估算为toeplitz协方差估计。 在特殊情况下，当$ \mathbfς$是一个低级别的toeplitz矩阵时，我们的结果与最先进的相匹配，并提供了更简单的证明。我们还提供了一个信息理论下限，将上限匹配到因子$ d $，并讨论缩小此差距的一些方向。
We study the sample complexity of estimating the covariance matrix $\mathbfΣ \in \mathbb{R}^{d\times d}$ of a distribution $\mathcal D$ over $\mathbb{R}^d$ given independent samples, under the assumption that $\mathbfΣ$ is graph-structured. In particular, we focus on shortest path covariance matrices, where the covariance between any two measurements is determined by the shortest path distance in an underlying graph with $d$ nodes. Such matrices generalize Toeplitz and circulant covariance matrices and are widely applied in signal processing applications, where the covariance between two measurements depends on the (shortest path) distance between them in time or space. We focus on minimizing both the vector sample complexity: the number of samples drawn from $\mathcal{D}$ and the entry sample complexity: the number of entries read in each sample. The entry sample complexity corresponds to measurement equipment costs in signal processing applications. We give a very simple algorithm for estimating $\mathbfΣ$ up to spectral norm error $ε\left\|\mathbfΣ\right\|_2$ using just $O(\sqrt{D})$ entry sample complexity and $\tilde O(r^2/ε^2)$ vector sample complexity, where $D$ is the diameter of the underlying graph and $r \le d$ is the rank of $\mathbfΣ$. Our method is based on extending the widely applied idea of sparse rulers for Toeplitz covariance estimation to the graph setting. In the special case when $\mathbfΣ$ is a low-rank Toeplitz matrix, our result matches the state-of-the-art, with a far simpler proof. We also give an information theoretic lower bound matching our upper bound up to a factor $D$ and discuss some directions towards closing this gap.
