An affine scaling methodology for best basis selection

A methodology is developed to derive algorithms for optimal basis selection by minimizing diversity measures proposed by Wickerhauser and Donoho. Thes e measures include the p-norm-like (l((p less than or equal to 1))) diversi ty measures and the Gaussian and Shannon entropies. The algorithm developme nt methodology uses a factored representation for the gradient and involves successive relaxation of the Lagrangian necessary condition. This yields a lgorithms that are intimately related to the Affine Scaling Transformation (AST) based methods commonly employed by the interior point approach to non linear optimization. The algorithms minimizing the l((p less than or equal to 1)) diversity measures are equivalent to a recently developed class of a lgorithms called FOCal Underdetermined System Solver (FOCUSS). The general nature of the methodology provides a systematic approach for deriving this class of algorithms and a natural mechanism for extending them. It also fac ilitates a better understanding of the convergence behavior and a strengthe ning of the convergence results. The Gaussian entropy minimization algorith m is shown to be equivalent to a well-behaved p = 0 norm-like optimization algorithm. Computer experiments demonstrate that the p-norm-like and the Ga ussian entropy algorithms perform well, converging to sparse solutions. The Shannon entropy algorithm produces solutions that are concentrated but are shown to not converge to a fully sparse solution.