In this paper, we introduce nonlinear regularized wavelet estimators for estimating nonparametric regression functions when sampling points are not uniformly spaced. The approach can apply readily to many other statistical contexts. various new penalty functions are proposed. The hard-thresholding and soft-thresholding estimators of Donoho and Johnstone (1991) are specific members of nonlinear regularized wavelet estimators. They correspond to the lower and upper bound of a class of the penalized least-squares estimators. Necessary conditions for penalty functions are given for regularized estimators to possess thresholding properties. Oracle inequalities and universal thresholding parameters are obtained for a large class of penalty functions. The sampling properties of nonlinear regularized wavelet estimators are established, and are shown to be adaptively minimax. To efficiently solve penalized least-squares problems, Nonlinear Regularized Sobolev Interpolators (NRSI) are proposed as initial estimators, which are shown to have good sampling properties. The NRSI is further ameliorated by Regularized One-Step Estimators (ROSE), which are the one-step estimators of the penalized least-squares problems using the NRSI as initial estimators. Two other approaches, the graduated nonconvexity algorithm and wavelet networks, are also introduced to handle penalized least-squares problems. The newly introduced approaches are also illustrated by a few numerical examples.