Least Squares Isotonic Regression in Two Dimensions

Spouge, J.; Wan, H.; Wilbur, W.J.
June 2003
Journal of Optimization Theory & Applications;Jun2003, Vol. 117 Issue 3, p585
Academic Journal
Given a finite partially-ordered set with a positive weighting function defined on its points, it is well known that any real-valued function defined on the set has a unique best order-preserving approximation in the weighted least squares sense. Many algorithms have been given for the solution of this isotonic regression problem. Most such algorithms either are not polynomial or they are of unknown time complexity. Recently, it has become clear that the general isotonic regression problem can be solved as a network flow problem in time O(n[sup 4]) with a space requirement of O(n²), where n is the number of points in the set. Building on the insights at the basis of this improvement, we show here that, in the case of a general two-dimensional partial ordering, the problem can be solved in O(n³) time and, when the two-dimensional set is restricted to a grid, the time can be further improved to O(n²).


Related Articles

  • Statistical Measures for Least Squares Using the αQβR Algorithm. Kalaba, R. E.; Johnson, J.; Natsuyama, H. H. // Journal of Optimization Theory & Applications;Dec2005, Vol. 127 Issue 3, p515 

    This paper shows how the output derived from the αQβR algorithm can be used to calculate various statistical quantities needed to evaluate linear models. In particular, we show how to calculate standard statistical quantities like the coefficient of determination R2, the F-statistics, and...

  • An efficient algorithm for structured sparse quantile regression. Nassiri, Vahid; Loris, Ignace // Computational Statistics;Oct2014, Vol. 29 Issue 5, p1321 

    An efficient algorithm is derived for solving the quantile regression problem combined with a group sparsity promoting penalty. The group sparsity of the regression parameters is achieved by using a $$\ell _{1,\infty }$$ -norm penalty (or constraint) on the regression parameters. The algorithm...

  • Statistical Measures for Ordinary Least Squares Using the αQ Algorithm. Johnson, J.; Kalaba, R.E. // Journal of Optimization Theory & Applications;Jun2003, Vol. 117 Issue 3, p461 

    This paper shows how the dynamic program algorithm called the αQ algorithm can be used as an alternative algorithm to produce the coefficients of a least squares problem. It shows also how the output of the algorithm can be used to calculate various statistical quantities needed to evaluate...

  • Information criteria for variable selection under sparsity. Jansen, Maarten // Biometrika;Mar2014, Vol. 101 Issue 1, p37 

    The optimization of an information criterion in a variable selection procedure leads to an additional bias, which can be substantial for sparse, high-dimensional data. One can compensate for the bias by applying shrinkage while estimating within the selected models. This paper presents modified...

  • Optimization Study of Stepwise Regression and Partial Least Squares Regression Models for Dam Security Monitoring. Wei-ling HU; Nian-wu DENG; Qiu-shi LIU // Applied Mechanics & Materials;2014, Issue 578-579, p1101 

    Both Stepwise Regression (SR) and Partial Least Squares Regression (PLSR) can be applied in data analysis of dam security monitoring, and achieve in fitting and forecasting. However, SR and PLSR models still can be optimized. A variety of programs are studied and compared based on actual dam...

  • Robust Estimations as a Remedy for Multicollinearity Caused by Multiple High Leverage Points. Bagheri, Arezoo; Midi, Habshah // Journal of Mathematics & Statistics;2009, Vol. 5 Issue 4, p311 

    Problem statement: The Least Squares (LS) method has been the most popular technique for estimating the parameters of a model due to its optimal properties and ease of computation. LS estimated regression may be seriously disturbed by multicollinearity which is a near linear dependency between...

  • UN MODEL DE OPTIMIZARE PENTRU DATE FUZZY AN OPTIMIZATION MODEL FOR FUZZY DATA. POPESCU, Costin-Ciprian // Studii si Cercetari de Calcul Economic si Cibernetica Economica;2012, Vol. 46 Issue 3/4, p1 

    An optimization procedure for fuzzy data is presented. A regression model is employed for a particular set of nonlinear fuzzy numbers. The resulting algorithm is discussed and compared with some previous ones.

  • A Procedure for Optimal Stepwise MSAE Regression Analysis. Roodman, Gary M. // Operations Research;Mar/Apr74, Vol. 22 Issue 2, p393 

    This paper brings together two topics from regression analysis. One is the topic of stepwise regression, a set of commonly used procedures for exploring alternative formulations of the regression model. The other topic is regression by minimizing the sum of the absolute errors about the...

  • Probability-based least square support vector regression metamodeling technique for crashworthiness optimization problems. Wang, Hu; Li, Enying; Li, G. // Computational Mechanics;Mar2011, Vol. 47 Issue 3, p251 

    This paper presents a crashworthiness design optimization method based on a metamodeling technique. The crashworthiness optimization is a highly nonlinear and large scale problem, which is composed various nonlinearities, such as geometry, material and contact and needs a large number expensive...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics