The Column Subset Selection Problem (CSSP) and the Nystr\"om method are among
the leading tools for constructing small low-rank approximations of large
datasets in machine learning and scientific computing. A fundamental question
in this area is: how well can a data subset of size k compete with the best
rank k approximation? We develop techniques which exploit spectral properties
of the data matrix to obtain improved approximation guarantees which go beyond
the standard worst-case analysis. Our approach leads to significantly better
bounds for datasets with known rates of singular value decay, e.g., polynomial
or exponential decay. Our analysis also reveals an intriguing phenomenon: the
approximation factor as a function of k may exhibit multiple peaks and valleys,
which we call a multiple-descent curve. A lower bound we establish shows that
this behavior is not an artifact of our analysis, but rather it is an inherent
property of the CSSP and Nystr\"om tasks. Finally, using the example of a
radial basis function (RBF) kernel, we show that both our improved bounds and
the multiple-descent curve can be observed on real datasets simply by varying
the RBF parameter.

本文提出了利用数据矩阵的谱属性来获得改进的逼近保证，超越了标准的最坏情况分析，研究结果显示：逼近因子作为 k 的函数可能会呈现多个波峰和波谷，这被称为多峰曲线。

对于纵列子集选择和 Nyström 方法的改进保证和多下降曲线

Improved guarantees and a multiple-descent curve for Column Subset  Selection and the Nyström method

Generative Adversarial Networks (GANs), though powerful, is hard to train.
Several recent works (brock2016neural,miyato2018spectral) suggest that
controlling the spectra of weight matrices in the discriminator can
significantly improve the training of GANs. Motivated by their discovery, we
propose a new framework for training GANs, which allows more flexible spectrum
control (e.g., making the weight matrices of the discriminator have slow
singular value decays). Specifically, we propose a new reparameterization
approach for the weight matrices of the discriminator in GANs, which allows us
to directly manipulate the spectra of the weight matrices through various
regularizers and constraints, without intensively computing singular value
decompositions. Theoretically, we further show that the spectrum control
improves the generalization ability of GANs. Our experiments on CIFAR-10,
STL-10, and ImageNet datasets confirm that compared to other methods, our
proposed method is capable of generating images with competitive quality by
utilizing spectral normalization and encouraging the slow singular value decay.

通过引入新的重新参数化方法和对权重矩阵的光谱进行控制，使生成对抗网络在图像生成方面取得了更好的表现。