Convex Optimization 2026, 23 - Robust Approximation & Function Families

An approximation with the objective ||Ax - b|| and some uncertainty in the data matrix A are subject to stochastic robust approximation. The variation in A can be modeled through a random matrix with zero mean (note U). The problem can be solved when A assumes only a finite number of values prob(A = A_i) = p_i. Minimizing the sum over all entries is the sum-of-norms problem, expressed through minimizing p^Tt and subject to ||A_ix - b|| ≤ t_i (6.4.1). The variation could also be modeled through defining a set of possible values for A, which is assumed nonempty and bounded. In this case, define the worst-case error as e_wc(x) = sup{||Ax - b||: A ∈ 𝔸}. If 𝔸 is singleton, the problem reduces to the basic norm approximation problem (6.4.2, p. 319). Characteristics of 𝔸 can further characterize the problem. The noise term v in y = Ax + v is the additive noise, while the variation in A itself is the multiplicative error. If it's a finite set, then the problem becomes equivalent to that of the robust approximation problem with a polyhedral set, which can be cast into epigraph form. For various special bounded sets, the worst case error can be identified generically (p. 321 - 324).

A family of functions with a common domain can have each member associated with a point x, so that a function f(u) = ∑x_if_i(u) can be associated as in basis functions for the domain D. The family of Polynomials can be built, for example by the powers of the variable, or by the Lagrange basis. Piecewise linear functions can be built through triangularization of the domain (i.e. partitioning the set into a set of simplexes, which is the convex hull of the mesh' grid points) (6.5.1).