Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

A method of virtual displacements for the degenerate discrete $ l\sb{1}$ approximation problem


Authors: W. Fraser and J. M. Bennett
Journal: Math. Comp. 32 (1978), 421-430
MSC: Primary 41A50
MathSciNet review: 0487191
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Given the system of equations

$\displaystyle \sum\limits_{j = 1}^n {{a_{ij}}{x_j} = {b_i},\quad i = 1, \ldots ,m,} $

let $ {A_i} = ({a_{i1}}, \ldots ,{a_{in}})$. It is known that if the matrix $ A = ({a_{ij}})$ has rank $ k \leqslant n$, then there is a point X which provides a minimum of

$\displaystyle R(X) = \sum\limits_{i = 1}^m {\vert{r_i}(X)\vert = } \sum\limits_{i = 1}^m {\vert({A_i},X) - {b_i}\vert} $

such that $ {r_i}(X) = 0$ for at least k values of the index i. If $ {r_i}(X) = 0$ for exactly k values of the index i, the point or vertex is called ordinary, while if $ {r_i}(X) = 0$ for more than k values of i, the vertex is termed degenerate.

A necessary and sufficient condition to determine if X minimizes R is valid if X is an ordinary vertex but not if X is degenerate. A degeneracy at X can be removed by applying perturbations to an appropriate number of the $ {b_i}$ so that X becomes an ordinary vertex of a modified problem. By noting that the test uses only values of the $ {A_i}$, it is possible to avoid actual introduction of the perturbations to the $ {b_i}$ with a resulting substantial improvement of the efficiency of the computation.


References [Enhancements On Off] (What's this?)

  • [1] I. BARRODALE & F. D. K. ROBERTS, "Solution of an overdetermined system of equations in the $ {l_1}$ norm," Comm. ACM, v. 17, 1974.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 41A50

Retrieve articles in all journals with MSC: 41A50


Additional Information

DOI: http://dx.doi.org/10.1090/S0025-5718-1978-0487191-8
PII: S 0025-5718(1978)0487191-8
Article copyright: © Copyright 1978 American Mathematical Society