majorizationminimization

Majorization-Minimization (MM) is an iterative algorithm used for finding a local minimum of a function. It works by constructing a surrogate function that is easier to minimize and is guaranteed to lie above the original objective function. In each iteration, the algorithm minimizes this surrogate function, and the minimum of the surrogate becomes the starting point for the next iteration. This process ensures that the objective function value decreases or stays the same at each step, guaranteeing convergence to a local minimum.

The core idea is to replace a difficult minimization problem with a sequence of simpler ones. Let f(x) be the objective function we want to minimize. In each step k, we find a surrogate function g(x, x_k) such that f(x) <= g(x, x_k) for all x, and g(x_k, x_k) = f(x_k). The next estimate x_{k+1} is then chosen as the minimizer of g(x, x_k). Since f(x_{k+1}) <= g(x_{k+1}, x_k) and g(x_{k+1}, x_k) <= g(x_k, x_k) = f(x_k), we have f(x_{k+1}) <= f(x_k). This monotonic decrease ensures convergence.

The effectiveness of MM algorithms depends on the choice of the surrogate function. A good surrogate function should be easy to minimize and should closely approximate the original function near the current estimate. MM algorithms have found wide applications in various fields, including statistics, machine learning, and signal processing, particularly in problems involving maximum likelihood estimation and optimization of non-convex functions. Examples include algorithms for expectation-maximization, sparse signal recovery, and image reconstruction.