1. |
- Gulliksson, Mårten, et al.
(författare)
-
Algorithms for constrained and weighted nonlinear least squares
- 1997
-
Ingår i: SIAM Journal on Optimization. - 1052-6234 .- 1095-7189. ; 7:1, s. 208-224
-
Tidskriftsartikel (refereegranskat)abstract
- The authors consider constrained and weighted nonlinear least squares problems in which weights can be arbitrarily large. Methods of Newton type are used for solving such problems: a Gauss-Newton method, a second-order generalized Newton-Raphson method, and an efficient hybrid approach consisting of both methods are suggested. Local convergence and global convergence under certain assumptions are proved for the Gauss-Newton method. Results of computational testing of the algorithm suggested are presented and an open problem is formulated at the end of the paper.
|
|
2. |
- Gulliksson, Mårten, et al.
(författare)
-
Algorithms for constrained and weighted nonlinear least squares.
- 1997
-
Ingår i: SIAM Journal on Optimization. - 1052-6234. ; 7:1, s. 208-224
-
Tidskriftsartikel (refereegranskat)abstract
- A hybrid algorithm consisting of a Gauss--Newton method and a second-order method for solving constrained and weighted nonlinear least squares problems is developed, analyzed, and tested. One of the advantages of the algorithm is that arbitrarily large weights can be handled and that the weights in the merit function do not get unnecessarily large when the iterates diverge from a saddle point. The local convergence properties for the Gauss--Newton method are thoroughly analyzed and simple ways of estimating and calculating the local convergence rate for the Gauss--Newton method are given. Under the assumption that the constrained and weighted linear least squares subproblems attained in the Gauss--Newton method are not too ill conditioned, global convergence towards a first-order KKT point is proved.
|
|
3. |
- Gulliksson, Mårten, et al.
(författare)
-
Modifying the $QR$-decomposition to constrained and weighted linear least squares
- 1992
-
Ingår i: SIAM Journal on Matrix Analysis and Applications. - 0895-4798. ; 13:4, s. 1298-1313
-
Tidskriftsartikel (refereegranskat)abstract
- A new way of looking at a class of methods for the weighted linear least squares problem $min _x | M^{ - ( 1/2 )} ( b - Ax ) |_2 $ where $M = {operatorname{diag}}(mu _i )$ is presented by introducing a modified QR-decomposition with $Q$$M$-invariant, i.e., $QMQ^T = M$. One of the main advantages with this approach is that linear constraints are easily incorporated by letting the corresponding diagonal elements in $M$ become zero. Householder reflections are generalized to $M$-invariant reflections, and an algorithm for solving the constrained and weighted linear least squares problem is described. The system equations (or the augmented system equations) are used to derive condition numbers, and the connection between these condition numbers and the rounding error in the solution is investigated.
|
|
4. |
- Gulliksson, Mårten, et al.
(författare)
-
Perturbation theory for generalized and constrained linear least squares
- 2000
-
Ingår i: Numerical Linear Algebra with Applications. - 1070-5325. ; 7:4, s. 181-195
-
Tidskriftsartikel (refereegranskat)abstract
- The perturbation analysis of weighted and constrained rank-deficient linear least squares is difficult without the use of the augmented system of equations. In this paper a general form of the augmented system is used to get simple perturbation identities and perturbation bounds for the general linear least squares problem both for the full-rank and rank-deficient problem. Perturbation identities for the rank-deficient weighted and constrained case are found as a special case. Interesting perturbation bounds and condition numbers are derived that may be useful when considering the stability of a solution of the rank-deficient general least squares problem. Copyright © 2000 John Wiley & Sons, Ltd.
|
|
5. |
- Gulliksson, Mårten, et al.
(författare)
-
Using the nonlinear L-curve and its dual
- 1999
-
Ingår i: Progress in industrial mathematics at ECMI 98. - 3519026090 ; , s. 162-170
-
Konferensbidrag (övrigt vetenskapligt/konstnärligt)
|
|
6. |
- Nilsson, Thomas, 1978-
(författare)
-
Distributed Multiple Access and Service Differentiation Algorithms for Wireless Networks
- 2008
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Communicating over a wireless channel poses many unique challenges not found in wired communication because of the special characteristics of the wireless channel. The capacity in a wireless network is typically scarce as a result of the limited bandwidth and many distinct phenomenons, like attenuation and interference, that work destructively on the received signals.The Medium Access Control (MAC) layer is responsible for sharing this limited resource among the users. This allocation problem should be handled by considering the Quality of Service (QoS) requirements of each user as to maximize the utility. Efficient MAC algorithms are crucial in minimizing collisions between transmissions and thus achieving high utilization of the channel.This thesis focuses on conflict resolution and service differentiation algorithms for wireless local area networks, where there is no central control of the channel and each sender independently contends for access.In part I, we study three approaches to improve the IEEE 802.11(e) standards with focus on QoS. In the first approach, utility functions are considered, that model application preferences, to achieve service differentiation and maximize the aggregated utility. We provide algorithms for two subsidiary problems that arise from the maximization problem, and show that a near--optimal solution is found. In the second approach a collision detection algorithm for multicast transmissions is proposed, that increases the reliability for multicast compared to the protected unicast traffic. The third approach is an improved MAC algorithm for the QoS standard IEEE 802.11e. The improved algorithm outperforms the standard and achieves close to optimal performance for large number of scenarios, which significantly reduces the need of adjusting the contention parameters.In part II, we focus on channel bursting protocols that use noise bursts to resolve channel conflicts. These protocols is capable of achieving very low collision probability. We propose two new bursting protocols, that achieve very high channel utilization, and show that the bursting technique has good fairness properties and provides efficient support for service differentiation. We also show that it is possible to reduce the number of bursts without loosing performance.In part III, the optimal backoff distribution that minimizes the collision probability is derived. We then propose a heuristic backoff distribution with similar properties that yields high channel utilization. An extension for service differentiation is provided where the sizes of the backoff windows are adjusted.
|
|
7. |
- Söderkvist, Inge, et al.
(författare)
-
Determining the movements of the skeleton using well-configured markers
- 1993
-
Ingår i: Journal of Biomechanics. - 0021-9290 .- 1873-2380. ; 26, s. 1473-1477
-
Tidskriftsartikel (refereegranskat)abstract
- The problem of determining skeletal movements in 3 dimensions by using a number of landmarks is treated. We present a method that determines the motion of a rigid body by using the positions of the landmarks in a least-squares sense. The method uses the singular value decomposition of a matrix derived from the positions of the landmarks. We show how one can use this method to express movement of skeleton segments relative to each other. As many others have pointed out, the movement can be very ill determined if the landmarks are badly configured. We present a condition number for the problem with good geometrical properties. The condition number depends on the configuration of the landmarks and indicates how to distribute the landmarks in a suitable way.
|
|
8. |
- Söderkvist, Inge, et al.
(författare)
-
On condition numbers and algorithms for determining a rigid body movement
- 1994
-
Ingår i: BIT Numerical Mathematics. - 0006-3835 .- 1572-9125. ; 34:3, s. 424-436
-
Tidskriftsartikel (refereegranskat)abstract
- Using a set of landmarks to represent a rigid body, a rotation of the body can be determined in the least-squares sense as the solution of an orthogonal Procrustes problem. We discuss some geometrical properties of the condition number for the problem of determining the orthogonal matrix representing the rotation. It is shown that the condition number depends critically on the configuration of the landmarks. The problem is also reformulated as an unconstrained nonlinear least-squares problem and the condition number is related to the geometry of such problems. In the common 3-D case, the movement can be represented by using a screw axis. Also the condition numbers for the problem of determining the screw axis representation are shown to depend closely on the configuration of the landmarks. The condition numbers are finally used to show that the algorithms used are stable.
|
|
9. |
|
|
10. |
- Viklands, Thomas, 1971-
(författare)
-
Algorithms for the Weighted Orthogonal Procrustes Problem and other Least Squares Problems
- 2006
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- In this thesis, we present algorithms for local and global minimization of some Procrustes type problems. Typically, these problems are about rotating and scaling a known set of data to fit another set with applications related to determination of rigid body movements, factor analysis and multidimensional scaling. The known sets of data are usually represented as matrices, and the rotation to be determined is commonly a matrix Q with orthonormal columns.The algorithms presented use Newton and Gauss-Newton search directions with optimal step lengths, which in most cases result in a fast computation of a solution.Some of these problems are known to have several minima, e.g., the weighted orthogonal Procrustes problem (WOPP). A study on the maximal amount of minima has been done for this problem. Theoretical results and empirical observations gives strong indications that there are not more than 2n minimizers, where n is the number of columns in Q. A global optimization method to compute all 2n minima is presented.Also considered in this thesis is a cubically convergent iteration method for solving nonlinear equations. The iteration method presented uses second order information (derivatives) when computing a search direction. Normally this is a computational heavy task, but if the second order derivatives are constant, which is the case for quadratic equations, a performance gain can be obtained. This is confirmed by a small numerical study.Finally, regularization of ill-posed nonlinear least squares problems is considered. The quite well known L-curve for linear least squares problems is put in context for nonlinear problems.
|
|