Conditioning of Random Feature Matrices and Sparse Recovery

This thesis presents theoretical results in two areas. The first is conditioning of random feature matrices and the second is behaviors and convergence of weighted sparse identification of nonlinear dynamics (SINDy) algorithm.

The spectra of random feature matrices provide essential information on the conditioning of the linear system used in random feature regression problems and are thus connected to the consistency and generalization of random feature models. We provide (high probability) bounds on the concentration of singular values of random feature matrices. In particular, we show that if the complexity ratio N/m where m is the number of data samples and N is the number of random features scales like log(m) or log⁻¹ (N), then the random feature matrix is well-conditioned. When the dimension d is moderately large (e.g., d ≥ log(m) or d ≥ log(N)), the results hold in the setting when both data and features are random or one is random and the other is well-separated. For random Fourier feature matrix, we show that it satisfies s-restricted isometry property, and its s-restricted isometry constant is bounded if m scales like s log⁴ (N). We also derive upper bounds for the risk associated with regression problems using a random feature matrix in both the underparameterized setting and the overparameterized setting. This upper bound exhibits the double descent phenomenon and it is an effect of the double descent behavior of the condition number. Our bounds match the optimal scaling in the literature and the constants in our results are explicit and independent of the dimension of the data. 

The SINDy algorithm proposed in [18] is a sparsity-promoting algorithm. We generalize it to a weighted version which allows for the approximation of sparse vectors with small nonzero entries. We prove that the weighted SINDy algorithm has similar convergence properties and can approximate local minimizers of a non-convex objective function. Additionally, when prior information on the sparsity pattern of the target vector is available, we show that the optimization problem can be converted into an equivalent problem of smaller size, and weighted SINDy algorithm is able to recover partially sparse vectors. Numerical examples show that weighted SINDy algorithm can recovery the support more accurately than the original SINDy algorithm.