Sharp quadratic majorization in one dimension. (English) Zbl 1453.62078

Summary: Majorization methods solve minimization problems by replacing a complicated problem by a sequence of simpler problems. Solving the sequence of simple optimization problems guarantees convergence to a solution of the complicated original problem. Convergence is guaranteed by requiring that the approximating functions majorize the original function at the current solution. The leading examples of majorization are the EM algorithm and the SMACOF algorithm used in Multidimensional Scaling. The simplest possible majorizing subproblems are quadratic, because minimizing a quadratic is easy to do. In this paper quadratic majorizations for real-valued functions of a real variable are analyzed, and the concept of sharp majorization is introduced and studied. Applications to logit, probit, and robust loss functions are discussed.


62-08 Computational methods for problems pertaining to statistics
Full Text: DOI Link


[1] Böhning, D.; Lindsay, B.G., Monotonicity of quadratic approximation algorithms, Ann. inst. statist. math., 40, 641-663, (1988) · Zbl 0723.65150
[2] De Leeuw, J., Block relaxation algorithms in statistics, (), 308-325 · Zbl 0829.65144
[3] De Leeuw, J., Principal component analysis of binary data by iterated singular value decomposition, Comput. statist. data anal., 50, 21-39, (2006) · Zbl 1429.62218
[4] Dinkelbach, W., On nonlinear fractional programming, Manage. sci., 13, 492-498, (1967) · Zbl 0152.18402
[5] Groenen, P.J.F., Giaquinto, P., Kiers, H.A.L., 2003. Weighted majorization algorithms for weighted least squares decomposition models. Technical Report EI 2003-09, Econometric Institute, Erasmus University, Rotterdam, Netherlands
[6] Groenen, P.J.F.; Nalbantov, G.; Bioch, J.C., Nonlinear support vector machines through iterative majorization and I-splines, (), 149-161
[7] Groenen, P.J.F.; Nalbantov, G.; Bioch, J.C., SVM-maj: A majorization approach to linear support vector machines with different hinge errors, Adv. data anal. classification, 2, 17-43, (2008) · Zbl 1151.90551
[8] Heiser, W.J., 1986. A majorization algorithm for the reciprocal location problem. Technical Report RR-86-12. Department of Data Theory, University of Leiden, Leiden, Netherlands
[9] Heiser, W.J., Correspondence analysis with least absolute residuals, Comput. statist. data anal., 5, 337-356, (1987) · Zbl 0624.62052
[10] Heiser, W.J., Convergent computation by iterative majorization: theory and applications in multidimensional data analysis, (), 157-189
[11] Hunter, D.R.; Lange, K., A tutorial on MM algorithms, Amer. statist., 58, 30-37, (2004)
[12] Hunter, D.R.; Li, R., Variable selection using MM algorithms, Ann. statist., 33, 1617-1642, (2005) · Zbl 1078.62028
[13] Jaakkola, T.S.W.; Jordan, M.I.W., Bayesian parameter estimation via variational methods, Statist. comput., 10, 25-37, (2000)
[14] Lange, K., Optimization, (2004), Springer-Verlag New York · Zbl 1140.90004
[15] Lange, K.; Hunter, D.R.; Yang, I., Optimization transfer using surrogate objective functions (with discussion), J. comput. graph. statist., 9, 1-59, (2000)
[16] McShane, E.J., Integration, (1944), Princeton University Press Princeton
[17] Van Ruitenburg, J., 2005. Algorithms for parameter estimation in the Rasch model. Measurement and Research Department Reports 2005-04, Arnhem, Netherlands
[18] Vapnik, V., The nature of statistical learning theory, (1995), Springer-Verlag New York · Zbl 0833.62008
[19] Verboon, P.; Heiser, W.J., Resistant lower rank approximation of matrices by iterative majorization, Comput. statist. data anal., 18, 457-467, (1994) · Zbl 0825.65128
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.