Optimization

Distributed estimation of graphical models

Graphical models are commonly used to describe statistical relationships among a large number of variables, especially in networks such as sensor and social networks. Given the structure of a network, an important problem is to learn parameters associated with edges in the graph that represent correlations between connected nodes, e.g. individuals in a social network. We propose a distributed algorithm for estimating these inverse covariance parameters that decomposes the global problem, which is high-dimensional and communication-intensive, into low-dimensional problems solved at each node communicating only with its neighbors (see figure). Surprisingly, the distributed estimator nearly matches the much more expensive global estimator in terms of accuracy despite the near-absence of communication between neighborhoods. Convex relaxation is key to making our algorithm tractable and optimization theory aids in analyzing its favorable performance.

a large network
local neighborhood within larger graph

Left: A large network. Right: A local neighborhood centered at node i within a larger graph.

  • Z. Meng, D. Wei, A. Wiesel, A. O. Hero, "Marginal likelihoods for distributed parameter estimation of Gaussian graphical models," to appear in IEEE Transactions on Signal Processing, 2014. [arXiv]
  • Z. Meng, D. Wei, A. Wiesel, A. O. Hero, "Marginal likelihoods for distributed estimation of graphical model parameters," IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP), Saint Martin, December 2013. Best student paper award. [pdf] [IEEE Xplore]
  • Z. Meng, D. Wei, A. Wiesel, A. O. Hero, "Distributed learning of Gaussian graphical models via marginal likelihoods," 16th International Conference on Artificial Intelligence and Statistics (AISTATS), Scottsdale, AZ, April 2013. Notable paper award. [proceedings] [arXiv]

Sparse filter design

Digital filters are ubiquitous signal processing components, encompassing not only frequency selection but also linear sensor arrays and systems for signal detection and estimation such as equalizers for communication channels. The cost of implementing a filter, whether in terms of computation, power, or hardware, is often dominated by arithmetic operations and can therefore be reduced by designing sparse filters having few nonzero coefficients. Unfortunately, achieving the best trade-off between sparsity and filter performance is a difficult combinatorial optimization, differing from sparse linear inverse problems currently popular in signal processing and notably in compressive sensing.

sparse FIR filter

We approach the problem of sparse filter design from two directions. In the first approach, we have developed low-complexity algorithms that yield designs that are significantly sparser than conventional ones, in many instances optimally sparse for the given performance specifications. These algorithms use efficient optimization methods such as linear programming. We have also unified several sparse filter design problems with quadratic performance constraints (as well as other problems with the same mathematical form) by reducing them to a common canonical form, and have identified specific cases that admit efficient exact solutions. Applications include frequency selection, beamforming, and equalization for wireless channels and acoustic systems.

  • D. Wei, C. K. Sestok, A. V. Oppenheim, "Sparse filter design under a quadratic constraint: Low-complexity algorithms," IEEE Transactions on Signal Processing, vol. 61, no. 4, pp. 857-870, February 2013. [pdf] [IEEE Xplore]
  • T. Baran, D. Wei, and A. V. Oppenheim, "Linear programming algorithms for sparse filter design," IEEE Transactions on Signal Processing, vol. 58, pp. 1605-1617, March 2010. [pdf] [IEEE Xplore]
    • D. Wei, "Non-convex optimization for the design of sparse FIR filters," IEEE Workshop on Statistical Signal Processing (SSP), Cardiff, UK, September 2009. [pdf] [IEEE Xplore]

In the other direction, we have derived convex relaxations whose solutions bound the maximum sparsity for a given performance specification. These bounds certify whether a given design or algorithm is "good enough" and can also be leveraged to greatly reduce the complexity of solving the exact combinatorial problem in many cases. The relaxations come with analytical guarantees on the quality of approximation, yielding insight into the classes of problems for which they are most effective.

  • D. Wei and A. V. Oppenheim, "A branch-and-bound algorithm for quadratically-constrained sparse filter design," IEEE Transactions on Signal Processing, vol. 61, no. 4, pp. 1006-1018, February 2013. [pdf] [IEEE Xplore]
  • D. Wei and A. V. Oppenheim, "Sparsity maximization under a quadratic constraint with applications in filter design," IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), Dallas, TX, March 2010. [pdf] [IEEE Xplore]
  • D. Wei, "On two relaxations of quadratically-constrained cardinality minimization," October 2012. [arXiv]

This work has been extended to include filters that require fewer bits in the binary representation of the filter coefficients, an important consideration in fixed-point hardware implementations. Further details can be found in my doctoral thesis.

  • D. Wei, "Design of discrete-time filters for efficient implementation," Ph.D. thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, May 2011. [pdf]

Sparse partial least squares regression

Partial least squares (PLS) is a method for reducing the dimension of large datasets, like the more familiar method of principal component analysis (PCA), but unlike PCA, it does so while retaining the ability to predict a second set of response variables. In very high dimensions, it becomes desirable to combine PLS with variable selection. We propose a formulation that adds a group sparsity penalty to the PLS criterion and solve the resulting non-convex optimization using an augmented Lagrangian algorithm that has linear complexity in the ambient dimension. In a study predicting influenza symptoms from gene expression levels, our method results in improved predictions and a more interpretable selection of genes compared to conventional PLS.

  • T.-Y. Liu, L. Trinchera, A. Tenenhaus, D. Wei, A. O. Hero, "Global criteria for sparse penalized partial least squares," 59th ISI World Statistics Congress (WSC), Hong Kong, China, August 2013.
  • T.-Y. Liu, L. Trinchera, A. Tenenhaus, D. Wei, A. O. Hero, "A new criterion for sparse PLS regression," 20th International Conference on Computational Statistics (COMPSTAT), Limassol, Cyprus, August 2012.

Robust synthetic aperture radar imaging

Synthetic aperture radar (SAR) offers high-resolution, wide-area remote imaging but can suffer from severe quantization, saturation, and other data distortions due to limited transmission bandwidth from satellites. We propose an efficient optimization-based inverse problem approach to SAR image formation that is robust to such distortions, preserving image quality under saturation of 30% of the data values as seen below.

  • D. Wei and P. T. Boufounos, "Saturation-robust SAR image formation," IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), Prague, Czech Republic, May 2011. [pdf] [IEEE Xplore]

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.