Beyond worst-case greedy selection
We study why simple greedy algorithms can perform far better than worst-case theory predicts by identifying structure in the spectral landscape. For determinant maximization, stable-rank windows create broad success valleys, while sharp spectral drops produce unavoidable failure cliffs. This view connects matrix spectra to practical subset selection and gives stronger guarantees for random features, near-identity kernels, and spiked-plus-noise models.




