Convex Optimization 2026, 21 - Norm Approximation

The simplest norm approximation problem is an unconstrained problem that minimizes ||Ax - b||, where the approximate solution of Ax ≈ b in the norm, is one of the most immediate solutions, and the vector r = Ax - b is the residual for the problem. Assuming that generally, the columns of A are independent, and that for A ∈ ℝ^m×n; generally m ≥ n. For m = n, the optimal point is A^-1b, then assume that m > n (6.1.1.0). This problem is closely related to the regression problem by writing Ax = ∑x_ia_i (6.1.1.1). An extension of the norm approximation problem is the weighted norm approximation problem, minimizing ||W(Ax - b)||, where W is a weighting matrix (6.1.1.5). Similar approximations can depend on the norm, such as the Least-squares approximation (6.1.1.6), or the Chebyshev approximation (6.1.1.7). In l_p-norm approximation, the objective under the l_p-norm depends only on the amplitude distribution of the residuals. It can be generalized to the objective depending only on this distribution, which defines the penalty function approximation problem that minimizes ∑ϕ(r_i) with r = Ax - b. ϕ here is the penalty function (6.1.2.0). An outlier is defined as a measurement y_i = a_i^Tx + v_i where the noise v_i is relatively large. It's often associated with faulty data. Correcting for outliers can be accomplished by using penalty function approximation with a penalty function that tests for residual, and sets it to a reasonable constant (6.1.2.1). For small residuals, the least-squares approximation weighs uses weighting by phasing their contributions out. In contrast, penalty functions that put relatively large weight on small residuals tend to yield very small or near-zero optimal values (6.1.2.2).

A basic least norm problem minimizes ||x||, Ax = b where the solution always exists if the linear equations have a solution. It's a convex optimization problem. Assuming the rows of A are independent, so that if the number of rows and column is the same, the only feasible point is x = A^-1b. The least norm problem then is only interesting when there are fewer rows than columns (6.2.0). It can be formulated as a norm approximation problem by eliminating the equality constraint (6.2.1) or as a problem of optimal design (6.2.2). There are fewer measurements than parameters to estimate, so the measurements don't completely determine the vector of parameters x. Any fitting x is consistent with the solution. A good guess for x is likely to be small, and the least-norm problem aims to resolve to the smallest x (6.2.3).