It has been observed that the performances of many high-dimensional estimation problems are universal with respect to underlying sensing (or design) matrices. Specifically, matrices with markedly different constructions seem to achieve identical performance if they share the same spectral distribution and have ``generic'' singular vectors. We prove this universality phenomenon for the case of convex regularized least squares (RLS) estimators under a linear regression model with additive Gaussian noise. Our main contributions are two-fold: (1) We introduce a notion of universality classes for sensing matrices, defined through a set of deterministic conditions that fix the spectrum of the sensing matrix and precisely capture the previously heuristic notion of generic singular vectors; (2) We show that for all sensing matrices that lie in the same universality class, the dynamics of the proximal gradient descent algorithm for solving the regression problem, as well as the performance of RLS estimators themselves (under additional strong convexity conditions) are asymptotically identical. In addition to including i.i.d. Gaussian and rotational invariant matrices as special cases, our universality class also contains highly structured, strongly correlated, or even (nearly) deterministic matrices. Examples of the latter include randomly signed versions of incoherent tight frames and randomly subsampled Hadamard transforms. As a consequence of this universality principle, the asymptotic performance of regularized linear regression on many structured matrices constructed with limited randomness can be characterized by using the rotationally invariant ensemble as an equivalent yet mathematically more tractable surrogate.
翻译:观察到许多高维估计问题的性能在基本感测(或设计)矩阵方面是普遍的。具体地说,具有明显不同构造的矩阵,如果具有相同的光谱分布和“generic's ”单矢量,其性能似乎相同。我们用添加高尔西噪音的线性回归模型证明,对于曲线正统最小正方形(RLS)的测量器来说,这种普遍性现象是普遍的。我们的主要贡献是双重的:(1) 我们引入了感测矩阵普遍性类别的概念,通过一套确定性条件来确定感测矩阵的频谱范围,并准确地捕捉到以前通用单向矢量超量矢量的超值概念;(2) 我们显示,对于同一普遍性类别中的所有感测矩阵而言,对于解决回归问题的精度梯度梯度下降算法(RLS)的动态,以及RLS估测器本身(在额外强烈的凝聚度条件下)的性能是相同的。除了确定性条件之外,一套确定性基质的可测量和旋转性等等的定性矩阵,在特殊情况下,我们所签定的正常性基质的规律性基数,在结构结构上,也含有高度结构化的精确的变数,在亚性变压性矩阵中包括一个高度结构化的硬性变数的硬性变数。