Nonlinearities play a critical role in a large number of signal and information processing applications, including the areas of machine learning, imaging, signal processing, and wireless communication. Unfortunately, analyzing the fundamental properties of nonlinear systems and developing suitable parameter estimation algorithms are notoriously difficult tasks. In fact, many existing theoretical results and parameter estimation algorithms for such nonlinear systems rely on unrealistic assumptions on the system model. In this thesis, we jointly consider applications, models, algorithms, and theory in order to design new analysis and estimation methods that perform well under realistic conditions. We focus on three distinct applications of nonlinear estimation in wireless communications, imaging, and machine learning. We provide theoretical and numerical results for wireless systems (nonparametric and impairment-aware data detection), phase retrieval (recovering real- or complex-valued signals from correlated magnitude measurements), spectral initialization (computing accurate initializers for nonconvex optimization problems), and neural networks (initializing weights in neural networks). For each application, we devise new algorithms that benefit from one or more of the following advantages: Scalability to large problem sizes, absence of tuning parameters, robustness to system parameter mismatches and correlated measurements, low complexity, and low memory footprint. For all of the proposed algorithms, our numerical results with both real-world and synthetic data demonstrate that our algorithms are able to outperform existing estimation methods under realistic conditions.