标题： 从间接观测学习图模型的结构 显示英文标题

标题： Structure Learning in Graphical Models from Indirect Observations

摘要： 本文考虑了使用参数方法和非参数方法学习一个$p$维随机向量$X \in R^p$的图形结构的问题。与之前直接观测$x$的工作不同，我们研究了一种间接观测场景，即通过传感矩阵$A \in R^{d\times p}$收集样本$y$，并受到一些加性噪声$w$的污染，即$Y = AX + W$。 对于参数化方法，我们假设$X$服从高斯分布，即$x\in R^p\sim N(\mu, \Sigma)$和$\Sigma \in R^{p\times p}$。 我们首次证明，在不定感知系统 ($d < p$) 下，可以使用不足的样本数 ($n < p$) 正确恢复正确的图形结构。 特别是，我们证明了对于精确恢复，需要维度$d = \Omega(p^{0.8})$和样本数量$n = \Omega(p^{0.8}\log^3 p)$。 对于非参数方法，我们假设$X$的分布是非正态分布而不是高斯分布。 在温和的条件下，我们证明了我们的图结构估计器可以得到正确的结构。 我们得出最小样本数$n$和维数$d$分别为$n\gtrsim (deg)^4 \log^4 n$和$d \gtrsim p + (deg\cdot\log(d-p))^{\beta/4}$，其中 deg 是图形模型中的最大马尔可夫毯，$\beta > 0$是某个固定正值常数。 此外，我们得到了从间接观测和不精确的噪声分布知识中推导出的$X$的CDF估计误差的非渐近一致界。 据我们所知，这是首次推导出该界，并可能具有独立的兴趣。 针对真实数据和合成数据的数值实验验证了理论结果。 显示英文摘要

摘要： This paper considers learning of the graphical structure of a $p$-dimensional random vector $X \in R^p$ using both parametric and non-parametric methods. Unlike the previous works which observe $x$ directly, we consider the indirect observation scenario in which samples $y$ are collected via a sensing matrix $A \in R^{d\times p}$, and corrupted with some additive noise $w$, i.e, $Y = AX + W$. For the parametric method, we assume $X$ to be Gaussian, i.e., $x\in R^p\sim N(\mu, \Sigma)$ and $\Sigma \in R^{p\times p}$. For the first time, we show that the correct graphical structure can be correctly recovered under the indefinite sensing system ($d < p$) using insufficient samples ($n < p$). In particular, we show that for the exact recovery, we require dimension $d = \Omega(p^{0.8})$ and sample number $n = \Omega(p^{0.8}\log^3 p)$. For the nonparametric method, we assume a nonparanormal distribution for $X$ rather than Gaussian. Under mild conditions, we show that our graph-structure estimator can obtain the correct structure. We derive the minimum sample number $n$ and dimension $d$ as $n\gtrsim (deg)^4 \log^4 n$ and $d \gtrsim p + (deg\cdot\log(d-p))^{\beta/4}$, respectively, where deg is the maximum Markov blanket in the graphical model and $\beta > 0$ is some fixed positive constant. Additionally, we obtain a non-asymptotic uniform bound on the estimation error of the CDF of $X$ from indirect observations with inexact knowledge of the noise distribution. To the best of our knowledge, this bound is derived for the first time and may serve as an independent interest. Numerical experiments on both real-world and synthetic data are provided confirm the theoretical results.