scientific article; zbMATH DE number 3915531
data analysisdescent methodsdiscrete approximationleast squares regressionnon-differentiable convex programmingpolyhedral convex programmingscalingsimplex methodsubgradient methodstextbook
Classification and discrimination; cluster analysis (statistical aspects) (62H30) Linear regression; mixed models (62J05) Research exposition (monographs, survey articles) pertaining to numerical analysis (65-02) Numerical smoothing, curve fitting (65D10) Numerical mathematical programming methods (65K05) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Linear programming (90C05) Convex programming (90C25)
Subject of the book are computational methods for discrete approximation problems. Given a set of n data (measurements) an element of a given, p- dimensional, linear space V of functions is sought such that the deviation from the data is minimized w.r.t. some norm. Mathematically the problem amounts to minimizing a function \(f(x)=\| Mx-f\|\), M an \(n\times p\) matrix, f the n-vector of data. Possibly the set of approximating functions may be further restricted to elements in V which satisfy additional linear constraints. Then f(x) is to be minimized subject to constraints Ax\(\leq b\). Choosing either \(\|\) \(\| =\|\) \(\|_ 1\) or \(\|\) \(\| =\|\) \(\|_{\infty}\) results in a function f being the pointwise maximum of finitely many affine functions (polyhedral convex function). Such problems - in an obvious way - can be restated as linear programming problems. Thus, in principle, \(\ell_ 1\) or \(\ell_{\infty}\) approximation may be considered either in the context of classical linear programming or in that of non-differentiable convex programming. Of course, the two approaches are strongly related if the second is restricted to polyhedral convex functions. In Chapters 3 and 4 for \(\ell_ 1\) and \(\ell_{\infty}\) approximation both approaches are considered. Chapters 1 and 2 give the theoretical and practical foundations. In Chapter 1 a short introduction into the theory of convex functions and convex programming is given, including conjugate functions and (Fenchel) duality. In addition, subgradient and \(\epsilon\)- subgradient methods are sketched forming the basis for the descent methods in Chapters 3 and 4. Chapter 2 is dedicated to the theory and computational methods for linear programming. In addition to the standard simplex method for equality constrained problems descent methods are considered for the inequality constraint case which are well-known specializations of reduced and projected gradient algorithms for general linearly constrained problems. Very valuable is the discussion of scaling - a point which usually receives too little attention in linear programming textbooks. In Chapter 5 least squares regression is considered including problems subject to linear constraints and so-called M-estimation. Chapter 6 comprises some applications to non-convex problems such as total approximation and cluster analysis. In a final Chapter a survey on complexity is given which includes the ellipsoid method and the work of Smale concerning the expected behavior of Lemke's algorithm. The book contains a lot of material for all of the above subjects and certainly the concentration on those aspects of (linear) programming that are relevant for data analysis is very attractive. Therefore, the book is surely valuable and recommendable for specialists in this field. Nevertheless, some critical remarks may be allowed. From the practical point of view it is surprising that much emphasize is given to the problem of degeneracy whereas numerical stability is treated quite incidentally. In the introduction the author states that the problem of manipulating sparse matrices is irrelevant for his considerations. This surely is true. Instead, however, the problem of ill-conditioning and numerical instability is more serious in practice than in most Operations Research applications. Moreover, in the preface applications to nonlinear problems are indicated which are iteratively solved by linearization. With respect to these, again it is surprising that the problem of finding and transmitting starting points for the algorithms is treated only incidentally. A second point of criticism is the rather accidental choice of literature included in the references. For instance, it is difficult to understand why - in dealing with descent methods for nondifferential programming - the work of for example Lemaréchal, Mifflin or the whole Russian school (Shor a.o.) are not even mentioned. Finally, the presentation often is unnecessarily complicated and yet indeterminate. Altogether, the book is surely useful for specialists as it contains a lot of details w.r.t. certain aspects of data-analysis. It seems less appropriate, however, for practitioners or as introductory text for students.
- Sensitivity analysis of constrained linear \(L_1\) regression: Perturbations to constraints, addition and deletion of observations
- Distance regression by Gauss-Newton-type methods and iteratively re-weighted least-squares
- On the solution of highly degenerate linear programmes
- Linear programming via least squares
- A globally and quadratically convergent affine scaling method for linear \(l_ 1\) problems
- Linear best approximation using a class of polyhedral norms
- The `lethargy' theorem - a property of approximation by \(\gamma\)- polynomials
- A practical anti-cycling procedure for linearly constrained optimization
- A new neural network for solving linear programming problems
- The relationship between theorems of the alternative, least norm problems, steepest descent directions, and degeneracy: A review
- On degeneracy in linear programming and related problems
- Methods of calculating \(l_ p\)-minimum norm solutions of consistent linear systems
- LAD regression for detecting outliers in response and explanatory variables
- Theorems of the alternative and duality
- A proximal point algorithm for minimax problems
- Discontinuous piecewise linear optimization
- Convergence behavior of an iterative reweighting algorithm to compute multivariate M-estimates for location and scatter
- Approximation in normed linear spaces
- The Gaussian hare and the Laplacian tortoise: computability of squared-error versus absolute-error estimators. With comments by Ronald A. Thisted and M. R. Osborne and a rejoinder by the authors
- An \(L_{1}\) estimation algorithm with degeneracy and linear constraints.
- Broken adaptive ridge regression and its asymptotic properties
- The geometry of basic, approximate, and minimum-norm solutions of linear equations
- An inexact algorithm for composite nondifferentiable optimization
- A note on the statistical properties of the secant algorithm for calculating rank estimators
- Finding normal solutions in piecewise linear programming
- Error estimates and Lipschitz constants for best approximation in continuous function spaces
- A method of Euclidean centers
- Incremental method for multiple line detection problem -- iterative reweighted approach
- A Laplacian approach to _1-norm minimization
- Robustness by reweighting for kernel estimators: an overview
- Iteratively reweighted least squares and slime mold dynamics: connection and convergence
- Data loci in algebraic optimization
- Incorporating LASSO effects into a mixed model for quantitative trait loci detection
- Nonlinear programming and nonsmooth optimization by successive linear programming
- A resilient domain decomposition polynomial chaos solver for uncertain elliptic PDEs
- An algorithm for fitting circular arcs to data using the \(l_1\) norm
- The distance between two convex sets
- Adaptive methods for solvings minimax problems∗
- Loss and retention of accuracy in affine scaling methods
- Discrete a priori bounds for the detection of corrupted PDE solutions in exascale computations
- Nonlinear residual minimization by iteratively reweighted least squares
- Necessary and Sufficient Conditions for Noiseless Sparse Recovery via Convex Quadratic Splines
- Conjugate gradient acceleration of iteratively re-weighted least squares methods
- Heuristic discrepancy principle for variational regularization of inverse problems
- Estimation of Polygons and Areas
- The influence function of penalized regression estimators
- Iteratively reweighted least squares minimization for sparse recovery
- Local properties of algorithms for minimizing nonsmooth composite functions
- A simple algebraic proof of Farkas's lemma and related theorems
- Convergence Behavior of the em algorithm for the multivariate t -distribution
- Semi-parametric MLE in Simple Linear Regression Analysis with Interval-Censored Data
- scientific article; zbMATH DE number 7246283 (Why is no real title available?)
- An algorithm for real and complex rational minimax approximation
- Quasi-linear compressed sensing
- Numerical Linear Approximation in C
- The best least absolute deviations line -- properties and two efficient methods for its derivation
- Robust Bayesian Regression Analysis Using Ramsay-Novick Distributed Errors with Student-t Prior
- A primal-dual algorithm for minimizing a sum of Euclidean norms
- An update-and-stabilize framework for the minimum-norm-point problem
- Numerical algorithms for estimation and calculation of parameters in modeling pest population dynamics and evolution of resistance
- Cardinality minimization, constraints, and regularization: a survey
- Iteratively reweighted least squares for phase unwrapping
- Cauchy graph convolutional networks
- Robust regression analysis using the weighted median model for improved denoising of MR data in image processing
- On the Wasserstein Median of Probability Measures
- Fast algorithms for _p-regression
- A general formulation of reweighted least squares fitting
- R-estimation in linear models: algorithms, complexity, challenges
- An update-and-stabilize framework for the minimum-norm-point problem
- The sagitta method for solving linear programs
- Smoothing methods for nonsmooth, nonconvex minimization
- Interpretable Model Summaries Using the Wasserstein Distance
- Three points method for searching the best least absolute deviations plane
- Local polynomial regression and filtering for a versatile mesh-free PDE solver
- Estimating the matrix p-norm
- On Hoffman's celebrated cycling LP example
- Smoothing Newton method for minimizing the sum of \(p\) -norms
- Sensitivity analysis of constrained linear L₁ regression: perturbations to response and predictor variables
- Computation of Huber's \(M\)-estimates for a block-angular regression problem
- When do stepwise algorithms meet subset selection criteria?
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3690974)