AWAlan. S. Willsky

Alan. S. Willsky

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Alan. S. Willsky has a total of 68 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Convex Solution to a Joint Attitude and Spin-Rate Estimation Problem

    by James Saunderson, Pablo A. Parrilo, Alan S. Willsky

    This paper considers the problem of jointly estimating the attitude and spin rate of a spinning spacecraft. Psiaki has formulated a family of optimization problems that generalize the classical least-squares attitude-estimation problem, known as Wahba’s problem, to the case of a spinning spacecraft. In the special case where the rotation axis and the fundamental sampling period are fixed and known, but the spin rate is unknown (such as for nutation-damped spin-stabilized spacecraft), Psiaki’s problem can be reformulated exactly as a type of tractable convex optimization problem called a semidefinite optimization problem. This reformulation allows the problem to be globally solved using standard numerical routines for semidefinite optimization.


  • Open Access

    A convex solution to Psiaki's first joint attitude and spin-rate estimation problem

    by James Saunderson, Pablo A. Parrilo, Alan S. Willsky

    We consider the problem of jointly estimating the attitude and spin-rate of a spinning spacecraft. Psiaki (J. Astronautical Sci., 57(1-2):73--92, 2009) has formulated a family of optimization problems that generalize the classical least-squares attitude estimation problem, known as Wahba's problem, to the case of a spinning spacecraft. If the rotation axis is fixed and known, but the spin-rate is unknown (such as for nutation-damped spin-stabilized spacecraft) we show that Psiaki's problem can be reformulated exactly as a type of tractable convex optimization problem called a semidefinite optimization problem. This reformulation allows us to globally solve the problem using standard numerical routines for semidefinite optimization. It also provides a natural semidefinite relaxation-based approach to more complicated variations on the problem.

  • Open Access

    Semidefinite descriptions of the convex hull of rotation matrices

    by James Saunderson, Pablo A. Parrilo, Alan S. Willsky

    We study the convex hull of $SO(n)$, thought of as the set of $n\times n$ orthogonal matrices with unit determinant, from the point of view of semidefinite programming. We show that the convex hull of $SO(n)$ is doubly spectrahedral, i.e. both it and its polar have a description as the intersection of a cone of positive semidefinite matrices with an affine subspace. Our spectrahedral representations are explicit, and are of minimum size, in the sense that there are no smaller spectrahedral representations of these convex bodies.

  • Open Access

    Learning Gaussian Graphical Models with Observed or Latent FVSs

    by Ying Liu, Alan S. Willsky

    Gaussian Graphical Models (GGMs) or Gauss Markov random fields are widely used in many applications, and the trade-off between the modeling capacity and the efficiency of learning and inference has been an important research problem. In this paper, we study the family of GGMs with small feedback vertex sets (FVSs), where an FVS is a set of nodes whose removal breaks all the cycles. Exact inference such as computing the marginal distributions and the partition function has complexity $O(k^{2}n)$ using message-passing algorithms, where k is the size of the FVS, and n is the total number of nodes. We propose efficient structure learning algorithms for two cases: 1) All nodes are observed, which is useful in modeling social or flight networks where the FVS nodes often correspond to a small number of high-degree nodes, or hubs, while the rest of the networks is modeled by a tree. Regardless of the maximum degree, without knowing the full graph structure, we can exactly compute the maximum likelihood estimate in $O(kn^2+n^2\log n)$ if the FVS is known or in polynomial time if the FVS is unknown but has bounded size. 2) The FVS nodes are latent variables, where structure learning is equivalent to decomposing a inverse covariance matrix (exactly or approximately) into the sum of a tree-structured matrix and a low-rank matrix. By incorporating efficient inference into the learning steps, we can obtain a learning algorithm using alternating low-rank correction with complexity $O(kn^{2}+n^{2}\log n)$ per iteration. We also perform experiments using both synthetic data as well as real data of flight delays to demonstrate the modeling capacity with FVSs of various sizes.

  • Open Access

    A New Class of Upper Bounds on the Log Partition Function

    by Martin Wainwright, Tommi S. Jaakkola, Alan Willsky

    Bounds on the log partition function are important in a variety of contexts, including approximate inference, model fitting, decision theory, and large deviations analysis. We introduce a new class of upper bounds on the log partition function, based on convex combinations of distributions in the exponential domain, that is applicable to an arbitrary undirected graphical model. In the special case of convex combinations of tree-structured distributions, we obtain a family of variational problems, similar to the Bethe free energy, but distinguished by the following desirable properties: i. they are cnvex, and have a unique global minimum; and ii. the global minimum gives an upper bound on the log partition function. The global minimum is defined by stationary conditions very similar to those defining fixed points of belief propagation or tree-based reparameterization Wainwright et al., 2001. As with BP fixed points, the elements of the minimizing argument can be used as approximations to the marginals of the original model. The analysis described here can be extended to structures of higher treewidth e.g., hypertrees, thereby making connections with more advanced approximations e.g., Kikuchi and variants Yedidia et al., 2001; Minka, 2001.

  • Top Cited Papers

    The Convex Geometry of Linear Inverse Problems

    by Venkat Chandrasekaran, Benjamin Recht, Pablo A. Parrilo, Alan S. Willsky


  • Open Access

    Bayesian Nonparametric Hidden Semi-Markov Models

    by Matthew J. Johnson, Alan S. Willsky

    There is much interest in the Hierarchical Dirichlet Process Hidden Markov Model (HDP-HMM) as a natural Bayesian nonparametric extension of the ubiquitous Hidden Markov Model for learning from sequential and time-series data. However, in many settings the HDP-HMM's strict Markovian constraints are undesirable, particularly if we wish to learn or encode non-geometric state durations. We can extend the HDP-HMM to capture such structure by drawing upon explicit-duration semi-Markovianity, which has been developed mainly in the parametric frequentist setting, to allow construction of highly interpretable models that admit natural prior information on state durations. In this paper we introduce the explicit-duration Hierarchical Dirichlet Process Hidden semi-Markov Model (HDP-HSMM) and develop sampling algorithms for efficient posterior inference. The methods we introduce also provide new methods for sampling inference in the finite Bayesian HSMM. Our modular Gibbs sampling methods can be embedded in samplers for larger hierarchical Bayesian models, adding semi-Markov chain modeling as another tool in the Bayesian inference toolbox. We demonstrate the utility of the HDP-HSMM and our inference methods on both synthetic and real experiments.

  • Feedback Message Passing for Inference in Gaussian Graphical Models

    by Ying Liu, Venkat Chandrasekaran, Animashree Anandkumar, Alan S. Willsky

    While loopy belief propagation (LBP) performs reasonably well for inference in some Gaussian graphical models with cycles, its performance is unsatisfactory for many others. In particular for some models LBP does not converge, and in general when it does converge, the computed variances are incorrect (except for cycle-free graphs for which belief propagation (BP) is non-iterative and exact). In this paper we propose feedback message passing (FMP), a message-passing algorithm that makes use of a special set of vertices (called a feedback vertex set or FVS) whose removal results in a cycle-free graph. In FMP, standard BP is employed several times on the cycle-free subgraph excluding the FVS while a special message-passing scheme is used for the nodes in the FVS. The computational complexity of exact inference is O(k2n), where is the number of feedback nodes, and is the total number of nodes. When the size of the FVS is very large, FMP is computationally costly. Hence we propose approximate FMP, where a pseudo-FVS is used instead of an FVS, and where inference in the non-cycle-free graph obtained by removing the pseudo-FVS is carried out approximately using LBP. We show that, when approximate FMP converges, it yields exact means and variances on the pseudo-FVS and exact means throughout the remainder of the graph. We also provide theoretical results on the convergence and accuracy of approximate FMP. In particular, we prove error bounds on variance computation. Based on these theoretical results, we design efficient algorithms to select a pseudo-FVS of bounded size. The choice of the pseudo-FVS allows us to explicitly trade off between efficiency and accuracy. Experimental results show that using a pseudo-FVS of size no larger than log (n), this procedure converges much more often, more quickly, and provides more accurate results than LBP on the entire graph.


  • Open Access

    Diagonal and Low-Rank Matrix Decompositions, Correlation Matrices, and Ellipsoid Fitting

    by James Saunderson, Venkat Chandrasekaran, Pablo A. Parrilo, Alan S. Willsky

    In this paper we establish links between, and new results for, three problems that are not usually considered together. The first is a matrix decomposition problem that arises in areas such as statistical modeling and signal processing: given a matrix $X$ formed as the sum of an unknown diagonal matrix and an unknown low rank positive semidefinite matrix, decompose $X$ into these constituents. The second problem we consider is to determine the facial structure of the set of correlation matrices, a convex set also known as the elliptope. This convex body, and particularly its facial structure, plays a role in applications from combinatorial optimization to mathematical finance. The third problem is a basic geometric question: given points $v_1,v_2,...,v_n\in \R^k$ (where $n > k$) determine whether there is a centered ellipsoid passing \emph{exactly} through all of the points. We show that in a precise sense these three problems are equivalent. Furthermore we establish a simple sufficient condition on a subspace $U$ that ensures any positive semidefinite matrix $L$ with column space $U$ can be recovered from $D+L$ for any diagonal matrix $D$ using a convex optimization-based heuristic known as minimum trace factor analysis. This result leads to a new understanding of the structure of rank-deficient correlation matrices and a simple condition on a set of points that ensures there is a centered ellipsoid passing through them.

  • Open Access

    The Convex Geometry of Linear Inverse Problems

    by Venkat Chandrasekaran, Benjamin Recht, Pablo A. Parrilo, Alan S. Willsky

    In applications throughout science and engineering one is often faced with the challenge of solving an ill-posed inverse problem, where the number of available measurements is smaller than the dimension of the model to be estimated. However in many practical situations of interest, models are constrained structurally so that they only have a few degrees of freedom relative to their ambient dimension. This paper provides a general framework to convert notions of simplicity into convex penalty functions, resulting in convex optimization solutions to linear, underdetermined inverse problems. The class of simple models considered are those formed as the sum of a few atoms from some (possibly infinite) elementary atomic set; examples include well-studied cases such as sparse vectors and low-rank matrices, as well as several others including sums of a few permutations matrices, low-rank tensors, orthogonal matrices, and atomic measures. The convex programming formulation is based on minimizing the norm induced by the convex hull of the atomic set; this norm is referred to as the atomic norm. The facial structure of the atomic norm ball carries a number of favorable properties that are useful for recovering simple models, and an analysis of the underlying convex geometry provides sharp estimates of the number of generic measurements required for exact and robust recovery of models from partial information. These estimates are based on computing the Gaussian widths of tangent cones to the atomic norm ball. When the atomic set has algebraic structure the resulting optimization problems can be solved or approximated via semidefinite programming. The quality of these approximations affects the number of measurements required for recovery. Thus this work extends the catalog of simple models that can be recovered from limited linear information via tractable convex programming.