An algorithm for non-negative norm minimal solutions (Q3777326)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4039130
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | An algorithm for non-negative norm minimal solutions |
scientific article; zbMATH DE number 4039130 |
Statements
An algorithm for non-negative norm minimal solutions (English)
0 references
1987
0 references
non-negative norm minimal solutions
0 references
iterative algorithm
0 references
overdetermined system
0 references
nonnegative least-squares solutions
0 references
0.8807044625282288
0 references
0.8806114196777344
0 references
0.8775135278701782
0 references
0.8722139000892639
0 references
Let \(Ax=b\) be an overdetermined system of linear equations. This paper provides an algorithm (and several variants of it) for solving the problem \((P)\quad \min \{| Ax-b\| /x\geq 0\},\) where \(\| \|\) is any strictly convex norm (e.g., an l p-norm with \(p\in]1,+\infty [)\). The algorithm is based on duality results of the following type: With \((P')\quad \max \{\{<b,z>\}/A\quad Tz\leq 0,\quad \| z\| '=1\},\) where \(\| \| '\) is the usual dual norm for \(\| \|\), the following holds: (P) and (P') have the same optimal values. If this value is strictly positive, then x solves (P) iff there is a y with \(\| y\| '=1\) and A Ty\(\leq 0\) such that \(Ax=b-<b,y>\cdot y'\). Moreover \(<y,Ax>>0\) and y solves (P'). (Here, y' is such that \(\| y'\| =1\) and \(<y',y>=\| y\| '\), which exists by the definition of \(\| \| ')\). The algorithm, which needs the computation of nonnegative least-squares solutions as a subroutine, generates two sequences \((x_ k)\) and \((y_ k)\). If it terminates, the respective final values solve (P) and (P'). Otherwise, each respective cluster point does. If \(\| \|\) is smooth, the sequence \((y_ k)\) converges. It may happen that \((x_ k)\) has no cluster points at all. However, from solutions of (P'), which are easier to obtain, a solution of (P) can be constructed via duality. The author also reports about the numerical performance of the algorithm and its variants. For an l p-norm with \(p\in]1,2[\), the algorithm works well, which is not the case for large values of p.
0 references