Sparsity and total variation regularization

For direct observations b, minimizing ||x−b||²/2+λ||x||₁ separates into scalar problems. Away from zero the derivative contains λ times the sign, while at zero the subgradient of absolute value is the interval from minus one to one. This gives soft thresholding: move a coefficient toward zero by λ, and set it exactly to zero if its magnitude is at most λ. The quadratic term makes this direct-observation problem strictly convex, so the resulting vector is unique.

For indirect data, minimizing ||Ax−y||²/2+λ||x||₁ is convex but need not be strictly convex when A has a nullspace. Existence, uniqueness, and recovery of the desired sparse object are separate questions. Under exact equality constraints, a useful sufficient condition for uniquely recovering an object supported on S is that every nonzero h in N(A) satisfy ||h_S||₁<||h_(S complement)||₁. The triangle inequality then shows that adding h increases the norm. Sparsity helps only when the measurements distinguish the relevant sparse alternatives.

For a one-dimensional chain, define (Dx)ᵢ=xᵢ₊₁−xᵢ and TV(x)=||Dx||₁. A constant signal has zero TV even when every pixel is nonzero. The penalty therefore favors piecewise-constant regions and a small total jump magnitude, rather than a mostly zero image. In two dimensions one must specify isotropic or anisotropic differences and boundary handling. Those choices change the discrete functional, so the term TV is not sufficient to reproduce an implementation numerically.

The nullspace of the difference operator contains constants. A TV penalty alone cannot determine an overall offset, and an indirect observation operator that also ignores constants leaves that ambiguity unresolved. With direct squared-error observations, the data term controls the mean and gives a unique minimizer. TV can preserve a sharp transition better than a squared-gradient penalty, but it also shrinks contrast and may create flat staircases. These are consequences of a structural model, not proof that every recovered edge is physically real.

Proximal and primal-dual algorithms can solve these convex objectives without differentiating absolute values at zero. A small optimality residual can certify that an algorithm solved the stated objective, yet cannot certify that the sparsity model matches the true object. The penalty parameter still balances data fit against structural bias. With a deterministic noise bound one can use an inequality-constrained formulation instead, but exact sparse recovery under noise needs quantitative properties of the observation operator and an appropriate error theorem.

Changing the representation changes what is sparse. A smooth oscillatory signal might have only a few Fourier coefficients but many nonzero finite differences, while a step signal is sparse in differences and has a long Fourier tail. It is therefore important to state the chosen basis, transform, or difference operator. Applying a sparsity penalty to a redundant transform also differs from choosing sparse synthesis coefficients. These distinctions affect identifiability, optimization variables, and the interpretation of uncertainty after reconstruction.