1
|
Zhou G, Tward D, Lange K. A Majorization-Minimization Algorithm for Neuroimage Registration. SIAM J Imaging Sci 2024; 17:273-300. [PMID: 38550750 PMCID: PMC10977051 DOI: 10.1137/22m1516907] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [What about the content of this article? (0)] [Affiliation(s)] [Abstract] [Key Words] [Grants] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 04/01/2024]
Abstract
Intensity-based image registration is critical for neuroimaging tasks, such as 3D reconstruction, times-series alignment, and common coordinate mapping. The gradient-based optimization methods commonly used to solve this problem require a careful selection of step-length. This limitation imposes substantial time and computational costs. Here we propose a gradient-independent rigid-motion registration algorithm based on the majorization-minimization (MM) principle. Each iteration of our intensity-based MM algorithm reduces to a simple point-set rigid registration problem with a closed form solution that avoids the step-length issue altogether. The details of the algorithm are presented, and an error bound for its more practical truncated form is derived. The performance of the MM algorithm is shown to be more effective than gradient descent on simulated images and Nissl stained coronal slices of mouse brain. We also compare and contrast the similarities and differences between the MM algorithm and another gradient-free registration algorithm called the block-matching method. Finally, extensions of this algorithm to more complex problems are discussed.
Collapse
Affiliation(s)
- Gaiting Zhou
- Computational Medicine, UCLA, Los Angeles, CA 90024 USA
| | - Daniel Tward
- Computational Medicine, UCLA, Los Angeles, CA 90024 USA
| | - Kenneth Lange
- Computational Medicine, UCLA, Los Angeles, CA 90024 USA
| |
Collapse
|
2
|
Won JH, Zhou H, Lange K. ORTHOGONAL TRACE-SUM MAXIMIZATION: APPLICATIONS, LOCAL ALGORITHMS, AND GLOBAL OPTIMALITY. SIAM J Matrix Anal Appl 2021; 42:859-882. [PMID: 34776610 PMCID: PMC8589322 DOI: 10.1137/20m1363388] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [What about the content of this article? (0)] [Affiliation(s)] [Abstract] [Key Words] [Grants] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 05/29/2023]
Abstract
This paper studies the problem of maximizing the sum of traces of matrix quadratic forms on a product of Stiefel manifolds. This orthogonal trace-sum maximization (OTSM) problem generalizes many interesting problems such as generalized canonical correlation analysis (CCA), Procrustes analysis, and cryo-electron microscopy of the Nobel prize fame. For these applications finding global solutions is highly desirable, but it has been unclear how to find even a stationary point, let alone test its global optimality. Through a close inspection of Ky Fan's classical result [Proc. Natl. Acad. Sci. USA, 35 (1949), pp. 652-655] on the variational formulation of the sum of largest eigenvalues of a symmetric matrix, and a semidefinite programming (SDP) relaxation of the latter, we first provide a simple method to certify global optimality of a given stationary point of OTSM. This method only requires testing whether a symmetric matrix is positive semidefinite. A by-product of this analysis is an unexpected strong duality between Shapiro and Botha [SIAM J. Matrix Anal. Appl., 9 (1988), pp. 378-383] and Zhang and Singer [Linear Algebra Appl., 524 (2017), pp. 159-181]. After showing that a popular algorithm for generalized CCA and Procrustes analysis may generate oscillating iterates, we propose a simple fix that provably guarantees convergence to a stationary point. The combination of our algorithm and certificate reveals novel global optima of various instances of OTSM.
Collapse
Affiliation(s)
- Joong-Ho Won
- Department of Statistics, Seoul National University, Seoul 08826, Korea
| | - Hua Zhou
- Department of Biostatistics, University of California, Los Angeles, CA 90095-1766 USA
| | - Kenneth Lange
- Departments of Computational Medicine, Human Genetics, and Statistics, University of California, Los Angeles, CA 90095 USA
| |
Collapse
|
3
|
Lin YQ, Zhang YS, Tian GL, Ma CX. Fast QLB algorithm and hypothesis tests in logistic model for ophthalmologic bilateral correlated data. J Biopharm Stat 2020; 31:91-107. [PMID: 33001745 DOI: 10.1080/10543406.2020.1814794] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [What about the content of this article? (0)] [Affiliation(s)] [Abstract] [Key Words] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 10/23/2022]
Abstract
In ophthalmologic or otolaryngologic studies, bilateral correlated data often arise when observations involving paired organs (e.g., eyes, ears) are measured from each subject. Based on Donner's model , in this paper, we focus on investigating the relationship between the disease probability and covariates (such as ages, weights, gender, and so on) via the logistic regression for the analysis of bilateral correlated data. We first propose a new minorization-maximization (MM) algorithm and a fast quadratic lower bound (QLB) algorithm to calculate the maximum likelihood estimates of the vector of regression coefficients, and then develop three large-sample tests (i.e., the likelihood ratio test, Wald test, and score test) to test if covariates have a significant impact on the disease probability. Simulation studies are conducted to evaluate the performance of the proposed fast QLB algorithm and three testing methods. A real ophthalmologic data set in Iran is used to illustrate the proposed methods.
Collapse
Affiliation(s)
- Yi-Qi Lin
- Department of Statistics, The Chinese University of Hong Kong, Shatin, N.T, Hong Kong, P. R. China
| | - Yu-Shun Zhang
- Department of Statistics and Data Science, Southern University of Science and Technology, Shenzhen, Guangdong Province, P. R. China
| | - Guo-Liang Tian
- Department of Statistics and Data Science, Southern University of Science and Technology, Shenzhen, Guangdong Province, P. R. China
| | - Chang-Xing Ma
- Department of Biostatistics, The State University of New York at Buffalo, Buffalo, New York, USA
| |
Collapse
|
4
|
Hu L, Lu W, Zhou J, Zhou H. MM ALGORITHMS FOR VARIANCE COMPONENT ESTIMATION AND SELECTION IN LOGISTIC LINEAR MIXED MODEL. Stat Sin 2019; 29:1585-1605. [PMID: 32523320 PMCID: PMC7286582 DOI: 10.5705/ss.202017.0220] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [What about the content of this article? (0)] [Affiliation(s)] [Abstract] [Key Words] [Grants] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/06/2022]
Abstract
Logistic linear mixed models are widely used in experimental designs and genetic analyses of binary traits. Motivated by modern applications, we consider the case of many groups of random effects, where each group corresponds to a variance component. When the number of variance components is large, fitting a logistic linear mixed model is challenging. Thus, we develop two efficient and stable minorization-maximization (MM) algorithms for estimating variance components based on a Laplace approximation of the logistic model. One of these leads to a simple iterative soft-thresholding algorithm for variance component selection using the maximum penalized approximated likelihood. We demonstrate the variance component estimation and selection performance of our algorithms by means of simulation studies and an analysis of real data.
Collapse
|
5
|
Feng W, Sarkar A, Lim CY, Maiti T. Variable selection for binary spatial regression: Penalized quasi-likelihood approach. Biometrics 2016; 72:1164-1172. [PMID: 27061299 DOI: 10.1111/biom.12525] [Citation(s) in RCA: 3] [Impact Index Per Article: 0.4] [Reference Citation Analysis] [What about the content of this article? (0)] [Affiliation(s)] [Abstract] [Key Words] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 10/01/2014] [Revised: 01/01/2016] [Accepted: 03/01/2016] [Indexed: 11/29/2022]
Abstract
We consider the problem of selecting covariates in a spatial regression model when the response is binary. Penalized likelihood-based approach is proved to be effective for both variable selection and estimation simultaneously. In the context of a spatially dependent binary variable, an uniquely interpretable likelihood is not available, rather a quasi-likelihood might be more suitable. We develop a penalized quasi-likelihood with spatial dependence for simultaneous variable selection and parameter estimation along with an efficient computational algorithm. The theoretical properties including asymptotic normality and consistency are studied under increasing domain asymptotics framework. An extensive simulation study is conducted to validate the methodology. Real data examples are provided for illustration and applicability. Although theoretical justification has not been made, we also investigate empirical performance of the proposed penalized quasi-likelihood approach for spatial count data to explore suitability of this method to a general exponential family of distributions.
Collapse
Affiliation(s)
| | - Abdhi Sarkar
- Michigan State University, East Lansing, Michigan 48824, U.S.A
| | | | - Tapabrata Maiti
- Michigan State University, East Lansing, Michigan 48824, U.S.A
| |
Collapse
|
6
|
Abstract
Matrix completion discriminant analysis (MCDA) is designed for semi-supervised learning where the rate of missingness is high and predictors vastly outnumber cases. MCDA operates by mapping class labels to the vertices of a regular simplex. With c classes, these vertices are arranged on the surface of the unit sphere in c - 1 dimensional Euclidean space. Because all pairs of vertices are equidistant, the classes are treated symmetrically. To assign unlabeled cases to classes, the data is entered into a large matrix (cases along rows and predictors along columns) that is augmented by vertex coordinates stored in the last c - 1 columns. Once the matrix is constructed, its missing entries can be filled in by matrix completion. To carry out matrix completion, one minimizes a sum of squares plus a nuclear norm penalty. The simplest solution invokes an MM algorithm and singular value decomposition. Choice of the penalty tuning constant can be achieved by cross validation on randomly withheld case labels. Once the matrix is completed, an unlabeled case is assigned to the class vertex closest to the point deposited in its last c - 1 columns. A variety of examples drawn from the statistical literature demonstrate that MCDA is competitive on traditional problems and outperforms alternatives on large-scale problems.
Collapse
Affiliation(s)
- Tong Tong Wu
- Associate Professor in the Departments of Biostatistics and Computational Biology, University of Rochester, NY 14642
| | - Kenneth Lange
- Professor of Biomathematics, Human Genetics, and Statistics at the University of California, Los Angeles, CA 90095
| |
Collapse
|
7
|
Abstract
Birth-death processes (BDPs) are continuous-time Markov chains that track the number of "particles" in a system over time. While widely used in population biology, genetics and ecology, statistical inference of the instantaneous particle birth and death rates remains largely limited to restrictive linear BDPs in which per-particle birth and death rates are constant. Researchers often observe the number of particles at discrete times, necessitating data augmentation procedures such as expectation-maximization (EM) to find maximum likelihood estimates. For BDPs on finite state-spaces, there are powerful matrix methods for computing the conditional expectations needed for the E-step of the EM algorithm. For BDPs on infinite state-spaces, closed-form solutions for the E-step are available for some linear models, but most previous work has resorted to time-consuming simulation. Remarkably, we show that the E-step conditional expectations can be expressed as convolutions of computable transition probabilities for any general BDP with arbitrary rates. This important observation, along with a convenient continued fraction representation of the Laplace transforms of the transition probabilities, allows for novel and efficient computation of the conditional expectations for all BDPs, eliminating the need for truncation of the state-space or costly simulation. We use this insight to derive EM algorithms that yield maximum likelihood estimation for general BDPs characterized by various rate models, including generalized linear models. We show that our Laplace convolution technique outperforms competing methods when they are available and demonstrate a technique to accelerate EM algorithm convergence. We validate our approach using synthetic data and then apply our methods to cancer cell growth and estimation of mutation parameters in microsatellite evolution.
Collapse
Affiliation(s)
- Forrest W Crawford
- Department of Biostatistics, Yale University, 60 College Street, Box 208034, New Haven, CT 06510 USA
| | - Vladimir N Minin
- Department of Statistics, University of Washington, Padelford Hall C-315, Box 354322, Seattle, WA 98195-4322 USA
| | - Marc A Suchard
- Department of Biomathematics, University of California Los Angeles, 6558 Gonda Building, Los Angeles, CA 90095-1766 USA ; Department of Biostatistics, University of California Los Angeles, 6558 Gonda Building, Los Angeles, CA 90095-1766 USA ; Department of Human Genetics, University of California Los Angeles, 6558 Gonda Building, Los Angeles, CA 90095-1766 USA
| |
Collapse
|
8
|
Abstract
Modern computational statistics is turning more and more to high-dimensional optimization to handle the deluge of big data. Once a model is formulated, its parameters can be estimated by optimization. Because model parsimony is important, models routinely include nondifferentiable penalty terms such as the lasso. This sober reality complicates minimization and maximization. Our broad survey stresses a few important principles in algorithm design. Rather than view these principles in isolation, it is more productive to mix and match them. A few well chosen examples illustrate this point. Algorithm derivation is also emphasized, and theory is downplayed, particularly the abstractions of the convex calculus. Thus, our survey should be useful and accessible to a broad audience.
Collapse
Affiliation(s)
- Kenneth Lange
- Departments of Biomathematics, Human Genetics, and Statistics University of California Los Angeles, CA 90095-1766
| | - Eric C Chi
- Department of Human Genetics University of California Los Angeles, CA 90095
| | - Hua Zhou
- Department of Statistics North Carolina State University Raleigh, NC 27695-8203
| |
Collapse
|
9
|
Abstract
This paper derives new algorithms for signomial programming, a generalization of geometric programming. The algorithms are based on a generic principle for optimization called the MM algorithm. In this setting, one can apply the geometric-arithmetic mean inequality and a supporting hyperplane inequality to create a surrogate function with parameters separated. Thus, unconstrained signomial programming reduces to a sequence of one-dimensional minimization problems. Simple examples demonstrate that the MM algorithm derived can converge to a boundary point or to one point of a continuum of minimum points. Conditions under which the minimum point is unique or occurs in the interior of parameter space are proved for geometric programming. Convergence to an interior point occurs at a linear rate. Finally, the MM framework easily accommodates equality and inequality constraints of signomial type. For the most important special case, constrained quadratic programming, the MM algorithm involves very simple updates.
Collapse
Affiliation(s)
- Kenneth Lange
- Departments of Biomathematics, Human Genetics, and Statistics, University of California, Los Angeles, CA 90095-1766, USA.
| | - Hua Zhou
- Department of Statistics, North Carolina State University, 2311 Stinson Drive, Campus Box 8203, Raleigh, NC 27695-8203, USA.
| |
Collapse
|
10
|
Abstract
The celebrated expectation-maximization (EM) algorithm is one of the most widely used optimization methods in statistics. In recent years it has been realized that EM algorithm is a special case of the more general minorization-maximization (MM) principle. Both algorithms creates a surrogate function in the first (E or M) step that is maximized in the second M step. This two step process always drives the objective function uphill and is iterated until the parameters converge. The two algorithms differ in the way the surrogate function is constructed. The expectation step of the EM algorithm relies on calculating conditional expectations, while the minorization step of the MM algorithm builds on crafty use of inequalities. For many problems, EM and MM derivations yield the same algorithm. This expository note walks through the construction of both algorithms for estimating the parameters of the Dirichlet-Multinomial distribution. This particular case is of interest because EM and MM derivations lead to two different algorithms with completely distinct operating characteristics. The EM algorithm converges fast but involves solving a nontrivial maximization problem in the M step. In contrast the MM updates are extremely simple but converge slowly. An EM-MM hybrid algorithm is derived which shows faster convergence than the MM algorithm in certain parameter regimes. The local convergence rates of the three algorithms are studied theoretically from the unifying MM point of view and also compared on numerical examples.
Collapse
Affiliation(s)
- Hua Zhou
- Department of Statistics, North Carolina State University, Raleigh, NC 27695-8203, USA
| | | |
Collapse
|