Stable recovery and the coordinate small-ball behaviour of random vectors
Stable recovery and the coordinate small-ball behaviour of random vectors
复制标题
随机向量的稳定恢复和坐标小球行为
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
G. Paouris
中科院分区：
文献类型：
--
作者：
S. Mendelson;G. Paouris
数据科学中的各种应用中的恢复过程都是基于EMPH(稳定点分离)的。在最简单的形式下，稳定点分离意味着如果$f$离$0$“很远”，并且给一个随机样本$(f(Z_I))_{i=1}^m$，其中一定比例的样本点可能被噪声破坏，该信息仍然足以证明$f$离$0$很远。
稳定点分离在IID抽样的背景下是很好理解的，为了探索一般抽样方法的稳定点分离，我们引入了一个新的概念-随机向量$X$的MPH{坐标小球}。粗略地说，此功能捕获了$(||)_{i=1}^m$的“相对较大的坐标”的数量，其中$T：mathbb{R}^n o mathbb{R}^m$是任意线性运算符，$(U_I)_{i=1}^m$是$mathbb{R}^m$的任意固定正交基。
我们证明了在关于$X$的裸极小假设下，许多值$||$的概率至少是$|T|_{S_2}/Sqrt{m}$的阶。因此，$Tx$的“坐标结构”表现出典型的欧几里德范数$Tx$，并且以一种稳定的方式进行。
我们分析的一个结果是，在生成随机向量的最小假设下，随机次采样卷积满足稳定点分离-这一事实以前只有在高度受限的设置中才知道，即对于具有iid亚高斯坐标的随机向量。
Recovery procedures in various application in Data Science are based on emph{stable point separation}. In its simplest form, stable point separation implies that if $f$ is "far away" from $0$, and one is given a random sample $(f(Z_i))_{i=1}^m$ where a proportional number of the sample points may be corrupted by noise, that information is still enough to exhibit that $f$ is far from $0$.
Stable point separation is well understood in the context of iid sampling, and to explore it for general sampling methods we introduce a new notion---the emph{coordinate small-ball} of a random vector $X$. Roughly put, this feature captures the number of "relatively large coordinates" of $(| |)_{i=1}^m$, where $T:mathbb{R}^n o mathbb{R}^m$ is an arbitrary linear operator and $(u_i)_{i=1}^m$ is any fixed orthonormal basis of $mathbb{R}^m$.
We show that under the bare-minimum assumptions on $X$, and with high probability, many of the values $| |$ are at least of the order $|T|_{S_2}/sqrt{m}$. As a result, the "coordinate structure" of $TX$ exhibits the typical Euclidean norm of $TX$ and does so in a stable way.
One outcome of our analysis is that random sub-sampled convolutions satisfy stable point separation under minimal assumptions on the generating random vector---a fact that was known previously only in a highly restrictive setup, namely, for random vectors with iid subgaussian coordinates.