ℓp-norm minimization plays a significant role in a variety of disciplines. It is not only important for the signal recovery in compressed sensing but also beneficial for finding meaningful signal representations as for the sparse and anti-sparse coding related applications. Therefore, minimizing ℓp-norms in an efficient manner sparked interest in a variety of works. This thesis is concerned with the noise-constrained ℓp-norm minimization for 1 ≤ p ≤ ∞. Although there are various optimization problem formulations that may be used to minimize an ℓp-norm, constraining the noise can offer a more meaningful optimization problem definition since when there is a known noise tolerance in an application, one can simply canalise it into the optimization problem and formulate exactly what to solve. Thus, it is often easier to set the noise tolerance from the optimization perspective. Despite this, there is a lack of computationally efficient algorithms in the literature for the noise-constrained ℓp-norm minimization problem because its feasible area can be complicated. Different optimization problem formulations can provide equivalent solutions and some of them might be easier to solve than the others. Therefore, it might be tempting to solve a computationally efficient problem in order to have the solution to another one. In this thesis, we solved constrained ℓp-norm regularization to reach the solution of the noise-constrained ℓp-norm problem. We introduce optimality tracing based ℓp-norm minimization approaches with simple root finding iterations for 1 ≤ p ≤ ∞. The optimality trade-off between both objectives, the ℓp-norm and a loss function that measures the data misfit, is formulated as a nonlinear equation root finding problem. We present and employ several simple, derivative-free and cost-efficient nonlinear equation root finding methods to trace this optimality over a Pareto frontier. Some of these root finding methods do not require differentiable loss functions and are applicable for both convex and nonconvex data misfits and extend such problems to a broader class of applications. We also introduce a warm-start strategy of taking linear least-squares solution with the one that has minimum ℓ2-norm which is named method of frames (MOF) as an input to require fewer iterations. This warm-start may provide flexible and meaningful starting point initialization for many applications where MOF already exists and can be improved with a better understanding of finitedimensional geometry, e.g. n-widths. The impact of the overcomplete matrix on the convergence rate of some of the presented approaches is demonstrated for matrices fulfilling the Uniform Uncertainty Principle and Uncertainty Principle. These properties were formerly introduced to analyze the performance of random matrices for ℓ1 and ℓ∞-norm related applications respectively. In the last part of the thesis, i.e. in Chapter 7, ℓp-norm minimization related applications are probed with using several loss functions such as least-squares, Huber and a nonconvex penalty Student’s t. ℓ1-norm is minimized with a typical compressed sensing example. Also, a generic test benchmark is utilized for the comparison of the nonlinear equation root finders for ℓ1-norm minimization. A new communication scheme is introduced by minimizing ℓ∞-norm. Outlier detection problem is studied with the minimized ℓ∞-norm, and a prior is offered for the minimized ℓ∞-norm with its performance on peak-to-average power ratio (PAPR). Noise-constrained nuclear norm is minimized as well for the Euclidean distance matrix completion problem with the application of wireless sensor network localization.