Skip to content Skip to navigation

Connexions

You are here: Home » Content » Iterative Reweighted Least Squares

Navigation

Recently Viewed

This feature requires Javascript to be enabled.
 

Iterative Reweighted Least Squares

Module by: C. Sidney Burrus. E-mail the author

Summary: Describes a powerful optimization algorithm which iteratively solves a weighted least squares approximation problem in order to solve an L_p approximation problem.

Approximation

Methods of approximating one function by another or of approximating measured data by the output of a mathematical or computer model are extraordinarily useful and ubiquitous. In this note, we present a very powerful algorithm most often called “Iterative Reweighted Least Squares” or (IRLS). Because minimizing the weighted squared error in an approximation can often be done analytically (or with a finite number of numerical calculations), it is the base of many iterative approaches. To illustrate this algorithm, we will pose the problem as finding the optimal approximate solution of a set of simultaneous linear equations

a 11 a 12 a 13 a 1 N a 21 a 22 a 23 a 31 a 32 a 33 a M 1 a M N x 1 x 2 x 3 x N = b 1 b 2 b 3 b M a 11 a 12 a 13 a 1 N a 21 a 22 a 23 a 31 a 32 a 33 a M 1 a M N x 1 x 2 x 3 x N = b 1 b 2 b 3 b M
(1)

or, in matrix notation

A x = b A x = b
(2)

where we are given an MM by NN real matrix AA and an MM by 1 vector bb, and want to find the NN by 1 vector xx. Only if AA is non-singular (square and full rank) is there a unique, exact solution. Otherwise, an approximate solution is sought according to some criterion of approximation.

If bb does not lie in the range space of AA (the space spanned by the columns of AA, [14]), there is no exact solution to Equation 2, therefore, an approximation problem is posed to be solved by minimizing the norm (or some other measure) of an equation error vector defined by

e = A x - b . e = A x - b .
(3)

A more general discussion of the solution of simultaneous equations can be found the the Connexions module [14].

Least Squared Error Approximation

A generalized solution (an optimal approximate solution) to Equation 2 is usually considered to be an xx that minimizes some norm or other measure of ee. If that problem does not have a unique solution, further conditions, such as also minimizing the norm of xx, are imposed and this combined problem always has a unique solution.

The l2l2 or root-mean-squared error or Euclidean norm is eTeeTe and its minimization has an analytical solution. This squared error is defined as

| | e | | 2 2 = i e i 2 = e T e | | e | | 2 2 = i e i 2 = e T e
(4)

which when minimized results in an exact or approximation solution of Equation 2 if AA has full row or column rank. The three cases are:

  • If AA has M=NM=N, (square and nonsingular), then the exact solution is
    x=A-1bx=A-1b
    (5)
  • If AA has M>NM>N, (over specified) then the approximate solution with the least squared equation error is
    x=[ATA]-1ATbx=[ATA]-1ATb
    (6)
  • If AA has M<NM<N, (under specified) then the approximate solution with the least norm is
    x=AT[AAT]-1bx=AT[AAT]-1b
    (7)

These formulas assume AA has full row or column rank but, if not, generalized solutions exist using the Moore-Penrose pseudoinverse [1], [10], [14].

Weighted Least Squared Error Approximation

In addition to these cases with “analytical” solutions, we can pose a more general problem by asking for an optimal approximation with a weighted norm [10], [11] to emphasize or de-emphasize certain components or range of equations. Here we minimize

| | We | | 2 2 = i w i 2 e i 2 = e T W T W e | | We | | 2 2 = i w i 2 e i 2 = e T W T W e
(8)

where WW is a diagonal matrix with the weights, wiwi, along its diagonal. The approximate solutions [14] are

  • If AA has M>NM>N, (over specified) then the minimum weighted equation error solution is
    x=[ATWTWA]-1ATWTWbx=[ATWTWA]-1ATWTWb
    (9)
  • If AA has M<NM<N, (under specified) then the minimum weighted norm solution is
    x=[WTW]-1ATA[WTW]-1AT-1bx=[WTW]-1ATA[WTW]-1AT-1b
    (10)

These solutions to the weighted approximation problem are useful in their own right but also serve as the foundation for the Iterative Reweighted Least Squares (IRLS) algorithm developed next.

Approximation with Other Norms and Error Measures

Most of the discussion about the approximate solutions to Ax=bAx=b are about the result of minimizing the l2l2 equation error ||Ax-b||2||Ax-b||2 and/or the l2l2 norm of the solution ||x||2||x||2 because in some cases that can be done by analytic formulas and also because the l2l2 norm has a energy interpretation. However, both the l1l1 and the ll norms [19] have well known applications that are important [21], [13] and use of the more general lplp error is remarkably flexible [3], [7]. Donoho has shown [22] that l1l1 optimization gives essentially the same sparsity as use of the true sparsity measure in l0l0.

The definition of the lplp norm of the vector xx for p greater than one is:

| | e | | p = i | e i | p 1 / p | | e | | p = i | e i | p 1 / p
(11)

which has the same solution for the minimum as

| | e | | p p = i | e i | p | | e | | p p = i | e i | p
(12)

but is often easier to use.

For the case where the rank is less than M or N, one can use one norm for the minimization of the equation error norm and another for minimization of the solution norm. And in other cases, one can simultaneously minimize a weighted error to emphasize some equations relative to others [10]. A modification allows minimizing according to one norm for one set of equations and another norm for a different set. A more general error measure than a norm can be used which uses a polynomial error [7] that does not satisfy the scaling requirement of a norm, but is convex. One could even use the so-called lplp norm for 1>p>01>p>0 which is not even convex but is an interesting tool for obtaining sparse solutions or discounting outliers. Still more unusual is the use of negative p.

Figure 1: Different lplp norms: p = .2, 1, 2, 10.
Figure 1 (power2.png)

Note from the figure how the l10l10 norm puts a large penalty on large errors. This gives a Chebyshev-like solution. The l0.2l0.2 norm puts a large penalty on small errors making them tend to zero. This (and the l1l1 norm) tends to discount "outliers" and give a sparse solution.

The lplp Norm Approximation

The IRLS (iterative reweighted least squares) algorithm allows an iterative algorithm to be built from the analytical solutions of the weighted least squares with an iterative reweighting to converge to the optimal lplp approximation [11], [37].

The Overdetermined System with more Equations than Unknowns

If one poses the lplp approximation problem in solving an overdetermined set of equations (case 2 from Chapter 3), it comes from defining the equation error vector

e = A x - b e = A x - b
(13)

and minimizing the p-norm defined in Equation 11 or, equivalently, Equation 12, neither of which can we minimize directly. However, we do have formulas [10] to find the minimum of the weighted squared error

| | W e | | 2 2 = n w n 2 | e n | 2 | | W e | | 2 2 = n w n 2 | e n | 2
(14)

one of which is

x = [ A T W T W A ] - 1 A T W T W b x = [ A T W T W A ] - 1 A T W T W b
(15)

where WW is a diagonal matrix of the error weights, wnwn.

Iteratively Reweighted Least Squares (IRLS)

If one poses the lplp approximation problem in solving an overdetermined set of equations (case 2 [14]), it comes from defining the equation error norm as

| | e | | p = n | e ( n ) | p 1 / p | | e | | p = n | e ( n ) | p 1 / p
(16)

and finding xx to minimizing this p-norm of the equation error.

It has been shown this is equivalent to solving a least weighted squared error problem for the appropriate weights.

| | e | | p = n w ( n ) 2 | e ( n ) | 2 1 / 2 | | e | | p = n w ( n ) 2 | e ( n ) | 2 1 / 2
(17)

If one takes Equation 16 and factors the term being summed in the following manor, comparison to Equation 17 suggests the iterative reweighted least algorithm which is the subject of these notes.

| | e | | p = n | e ( n ) | ( p - 2 ) | e ( n ) | 2 1 / p | | e | | p = n | e ( n ) | ( p - 2 ) | e ( n ) | 2 1 / p
(18)

To find the minimum lplp approximate solution, we propose the iterative reweighted least squared (IRLS) error algorithm which starts with unity weighting, W=IW=I, solves for an initial xx with Equation 15, calculates a new error from Equation 13, which is then used to set a new weighting matrix WW with diagonal elements of

w ( n ) = e ( n ) ( p - 2 ) / 2 w ( n ) = e ( n ) ( p - 2 ) / 2
(19)

to be used in the next iteration of Equation 15. Using this, we find a new solution xx and repeat until convergence (if it happens!). To guarantee convergence, this process should be a contraction map which converges to a fixed point that is the solution. A simple Matlab program that implements this algorithm is:

Listing 1: Program 1. Basic Iterative Reweighted Least Squares Algorithm
% m-file IRLS0.m to find the optimal solution to Ax=b
%  minimizing the L_p norm ||Ax-b||_p, using basic IRLS.
%  csb 11/10/2012
function x = IRLS0(A,b,p,KK)
if nargin < 4, KK=10;  end;
x  = pinv(A)*b;                              % Initial L_2 solution
E = [];
for k = 1:KK                                 % Iterate
   e  = A*x - b;                             % Error vector
   w  = abs(e).^((p-2)/2);                   % Error weights for IRLS
   W  = diag(w/sum(w));                      % Normalize weight matrix
   WA = W*A;                                 % apply weights
   x  = (WA'*WA)\(WA'*W)*b;                  % weighted L_2 sol.
   ee = norm(e,p);   E = [E ee];             % Error at each iteration
end
plot(E)

This core idea has been repeatedly proposed and developed in different application areas over the past 50 or so years with a variety of successes [11], [37], [3]. Used in this basic form, it reliably converges for 1.5<p<31.5<p<3. In 1970 [31], a modification was made by only partially updating the solution each iteration using

x ( k ) = q x ^ ( k ) + ( 1 - q ) x ( k - 1 ) x ( k ) = q x ^ ( k ) + ( 1 - q ) x ( k - 1 )
(20)

where x^x^ is the new weighted least squares solution of Equation 15 which is used to only partially update the previous value x(k-1)x(k-1) and k is the iteration index. The first use of this partial update optimized the value for qq on each iteration to give a more robust convergence but it slowed the total algorithm considerably.

A second improvement was made by using a specific up-date factor of

q = 1 p - 1 q = 1 p - 1
(21)

to significantly improve the rate of asymptotic convergence. With this particular factor and for p>2, the algorithm becomes a form of Newton's method which has quadratic asymptotic convergence [30], [7] but, unfortunately, the initial convergence became less robust.

A third modification applied homotopy [6], [45], [44], [47], [30], [24] by starting with a value for pp equal to 2 and increasing it each iteration (or the first few iterations) until it reached the desired value, or, in the case of p<2p<2, decreasing it. This improved the initial performance of the algorithm and made a significant increase in both the range of pp that allowed convergence and in the speed of calculations. Some of the history and details can be found applied to digital filter design in [3], [7].

A Matlab program that implements these ideas applied to our pseudoinverse problem with more equations than unknowns is:

Listing 2: Program 2. IRLS Algorithm with Newton's updating and Homotopy for M>N
% m-file IRLS1.m to find the optimal solution to Ax=b
%  minimizing the L_p norm ||Ax-b||_p, using IRLS.
%  Newton iterative update of solution, x, for  M > N.
%  For 2<p<infty, use homotopy parameter K = 1.01 to 2
%  For 0<p<2, use K = approx 0.7 - 0.9
%  csb 10/20/2012
function x = IRLS1(A,b,p,K,KK)
if nargin < 5, KK=10;  end;
if nargin < 4, K = 1.5;  end;
if nargin < 3, p = 10; end;
pk = 2;                                      % Initial homotopy value
x  = pinv(A)*b;                              % Initial L_2 solution
E = [];
for k = 1:KK                                 % Iterate
   if p >= 2, pk = min([p, K*pk]);           % Homotopy change of p
      else pk = max([p, K*pk]); end
   e  = A*x - b;                             % Error vector
   w  = abs(e).^((pk-2)/2);                  % Error weights for IRLS
   W  = diag(w/sum(w));                      % Normalize weight matrix
   WA = W*A;                                 % apply weights
   x1  = (WA'*WA)\(WA'*W)*b;                 % weighted L_2 sol.
   q  = 1/(pk-1);                            % Newton's parameter
   if p > 2, x = q*x1 + (1-q)*x; nn=p;       % partial update for p>2
      else x = x1; nn=2; end                 % no partial update for p<2
   ee = norm(e,nn);   E = [E ee];            % Error at each iteration
end
plot(E)

This can be modified to use different pp's in different bands of equations or to use weighting only when the error exceeds a certain threshold to achieve a constrained LS approximation [3], [7], [55].

Here, it is presented as applied to the overdetermined system (Case 2a and 2b [14]) but can also be applied to other cases. A particularly important application of this section is to the design of digital filters [7].

The Underdetermined System with more Unknowns than Equations

If one poses the lplp approximation problem in solving an underdetermined set of equations (case 3a [14]), it comes from defining the solution norm as

| | x | | p = n | x ( n ) | p 1 / p | | x | | p = n | x ( n ) | p 1 / p
(22)

and finding xx to minimizing this p-norm while satisfying Ax=bAx=b.

It also has been shown this is equivalent to solving a least weighted norm problem for specific weights.

| | x | | p = n w ( n ) 2 | x ( n ) | 2 1 / 2 | | x | | p = n w ( n ) 2 | x ( n ) | 2 1 / 2
(23)

The development follows the same arguments as in the previous section but using the formula [46], [10]

x = [ W T W ] - 1 A T A [ W T W ] - 1 A T - 1 b x = [ W T W ] - 1 A T A [ W T W ] - 1 A T - 1 b
(24)

with the weights, w(n)w(n), being the diagonal of the matrix, WW, in the iterative algorithm to give the minimum weighted solution norm in the same way as Equation 15 gives the minimum weighted equation error.

A Matlab program that implements these ideas applied to our pseudoinverse problem with more unknowns than equations is:

Listing 3: Program 3. IRLS Algorithm with Newton's updating and Homotopy for M less than N
% m-file IRLS2.m to find the optimal solution to Ax=b
%  minimizing the L_p norm ||x||_p, using IRLS.
%  Newton iterative update of solution, x, for  M < N.
%  For 2<p<infty, use homotopy parameter K = 1.01 to 2
%  For 0<p<2, use K = approx 0.7 to 0.9
%  csb 10/20/2012
function x = IRLS2(A,b,p,K,KK)
if nargin < 5, KK= 10;  end;
if nargin < 4, K = .8;  end;
if nargin < 3, p = 1.1; end;
pk = 2;                                 % Initial homotopy value
x  = pinv(A)*b;                         % Initial L_2 solution
E = [];
for k = 1:KK
   if p >= 2, pk = min([p, K*pk]);      % Homotopy update of p
      else pk = max([p, K*pk]); end
   W  = diag(abs(x).^((2-pk)/2)+0.00001);  % norm weights for IRLS
   AW = A*W;                            % applying new weights
   x1 = W*AW'*((AW*AW')\b);             % Weighted L_2 solution
   q  = 1/(pk-1);                       % Newton's parameter
   if p >= 2, x = q*x1 + (1-q)*x; nn=p; % Newton's partial update for p>2
      else x = x1; nn=1; end            % no Newton's partial update for p<2
   ee = norm(x,nn);  E = [E ee];        % norm at each iteration
end;
plot(E)

This approach is useful in sparse signal processing and for frame representation. Our work was originally done in the context of filter design but others have done similar things in sparsity analysis [28], [21], [59].

The methods developed here [3], [6] are based on the (IRLS) algorithm [50], [41], [12] and they can solve certain FIR filter design problems that neither the Remez exchange algorithm nor analytical L2L2 methods can.

History

The idea of using an IRLS algorithm to achieve a Chebyshev or LL approximation was first developed by Lawson in 1961 [32] and extended to LpLp by Rice and Usow in 1968 [42], [40]. The basic IRLS method presented here for LpLp was given by Karlovitz [31] and extended by Chalmers, et. al. [18], Bani and Chalmers [9], and Watson [58]. Independently, Fletcher, Grant and Hebden [25] developed a similar form of IRLS but based on Newton's method and Kahng [30] did likewise as an extension of Lawson's algorithm. Others analyzed and extended this work [24], [36], [12], [58]. Special analysis has been made for 1p<21p<2 by [53], [57], [41], [33], [36], [50], [60] and for p=p= by [25], [9], [41], [35], [2], [34]. Relations to the Remez exchange algorithm [19], [39] were suggested by [9], to homotopy [47], and to Karmarkar's linear programming algorithm [49] by [41], [48]. Applications of IRLS algorithms to complex Chebyshev approximation in FIR filter design have been made in [26], [20], [23], [52], [4] and to 2-D filter design in [17], [5]. Application to array design can be found in [51] and to statistics in [12].

The papers [7], [55] unify and extend the IRLS techniques and applies them to the design of FIR digital filters. They develops a framework that relates all of the above referenced work and shows them to be variations of a basic IRLS method modified so as to control convergence. In particular, [7] generalizes the work of Rice and Usow on Lawson's algorithm and explain why its asymptotic convergence is slow.

The main contribution of these recent papers is a new robust IRLS method for filter design [3], [6], [55] that combines an improved convergence acceleration scheme and a Newton based method. This gives a very efficient and versatile filter design algorithm that performs significantly better than the Rice-Usow-Lawson algorithm or any of the other IRLS schemes. Both the initial and asymptotic convergence behavior of the new algorithm is examined [55] and the reason for occasional slow convergence of this and all other IRLS methods is presented.

It is then shown that the new IRLS method allows the use of pp as a function of frequency to achieve different error criteria in the pass and stopbands of a filter. Therefore, this algorithm can be applied to solve the constrained LpLp approximation problem. Initial results of applications to the complex and two-dimensional filter design problem are also presented.

When used for the range 1<p<21<p<2, the new IRLS algorithm works well in outlier suppression in data and in finding sparsity for data compression.

Although the traditional IRLS methods were sometimes slower than competing approaches, the results of this paper and the availability of fast modern desktop computers make them practical now and allow exploitation of their greater flexibility and generality.

Convergence

Both theory and experience indicate there are different convergence problems connected with several different ranges and values of pp. In the range 1.5p<31.5p<3, virtually all methods converge [27], [12]. In the range 3p<3p<, the basic algorithm diverges and the various methods discussed in this paper must be used. As pp becomes large compared to 2, the weights carry a larger contribution to the total minimization than the underlying least squared error minimization, the improvement at each iteration becomes smaller, and the likelihood of divergence becomes larger. For p=p= the optimal approximation solution to Equation 2 is unique but the weights in Equation 6 that give that solution are not. In other words, different matrices WW give the same solution to Equation 2 but will have different convergence properties. This allows certain alteration to the weights to improve convergence without harming the optimality of the results [34].

In the range 1<p<21<p<2, both convergence and numerical problems exist as, in contrast to p>2p>2, the IRLS iterations are undoing what the underlying least squares is doing. In particular, the weights near frequencies with small errors become very large. Indeed, if the error happens to be zero, the weight becomes infinite because of the negative exponent in Equation 6. A small term can be added to the error to overcome this problem. For p=1p=1 the solution to the optimization problem is not even unique. The various algorithms that are presented are based on schemes to address these problems.

For some applications, the convergence is not robust. In these cases, the use of an adaptive step size can considerably improve convergence but at the expense of speed [55] [56]. For large and small pp, the weight functions wiwi are not unique even though the solution is unique [55]. This allows flexibility that prevents the occurrence of very large or very small weights [34].

One of the most versatile modifications of the basic IRLS algorithm is the use of different powers pp for different equations in Equation 2. For filters, this allows an l2l2 approximation in the passband and, simultaneously, an ll approximation in the stopband [7]. Another powerful modification is to use an polynomial error measure such as

q = i | e i | 2 + K | e i | 100 q = i | e i | 2 + K | e i | 100
(25)

in the IRLS algorithm. The first term dominates for ei<1ei<1 and the second term dominates for ei>1ei>1 which gives a constrained least squares approximation which is a very useful result [7], [16], [15], [55]. There are other modifications which can be made for specific applications where no alternative methods exist such as with 2D approximation [5] and cases where the error measure is not a norm nor even convex. Obviously, there are huge convergence problems but it is a good starting point. Still another application is to the design of recursive or IIR filters. It is possible to formulate these filters as a matrix multiplication and pose an iterative algorithm to find an optimal solution [54], [55], [38], [8].

A particular convergence problem that many iterative algorithms have is to have the error measure decrease for several iterations, then increase. This happens with Newton type algorithms when the function and its derivative are near zero giving a correction term approximately equal to zero over zero, or, indeterminate. This happens when finding a high order zero and that is similar to IRLS and ||e||p||e||p with a large p. One method used by Yagle [59] is to not iterate, but simply make one or two corrections for each of a fixed number of homotopy steps. This needs more investigation.

Summary

The individual ideas used in an IRLS program are

  • The basic IRLS algorithm of Equation 12,Equation 14,Equation 15,Equation 19 and Program 1. [32]
  • Adding a partial update to the iterations as in Equation 20 with optimization of the amount of update [31].
  • Choosing an update to give a Newton's method as in Equation 21 and Program 2. [25], [30]
  • Applying homotopy by increasing pp each iteration as in Program 2. [30], [24], [7]
  • Adaptive step size on partial updating and/or homotopy [56], [55]
  • Allowing pp to vary with different equations allowing a mixture of approximation criteria [4], [7]
  • Using p less than one, even zero. [59]
  • Using a polynomial error measure as in Equation 25 to give a near constrained least squares approximation. [7]
  • Using weighting envelops to stablize convergence for very large pp [55]
  • Applying IRLS to complex and 2D approximation, to Chebyshev and l1l1 approximation, to filter design, outlier supression in regression, and to creating sparse solutions [4], [5].

Iteratively Reweighted Least Squares (IRLS) approximation is a powerful and flexible tool for many engineering and applied problems. By combining several modifications to the basic IRLS algorithm, one can have a fast and robust approximation tool. But, while proofs of convergence can be given for individual parts of the combined algorithm, no formal proof seems to be possible for the combination.

Iterative Least Squares

The algorithm for iterative reweighted least squares approximation can be generalized to allow updates in the iterations other than on the weights. This is called iterative least squares and it includes IRLS as a special case where the iteration is on the weights. In all cases, the power and easy implementation of LS is the driving engine of the algorithm. In most, the algorithm is posed as a successive approximation in the form of a contraction map. An example of that is the design of a digital filter using optimal squared magnitude approximation. The ILS algorithm sets a desired magnitude frequency response and finds an optimal approximation to it by iteratively solving an optimal complex approximation (which we can easily do).

Start with a specified desired magnitude frequency response and no specified phase response. Applied a guess as to the phase response and construct the desired complex response. Find the optimal least squares complex approximation to that using formulas. Take the phase from that and apply it to the original desired magnitude. Then, do another complex approximation. In other words, we keep the ideal magnitude response and update the phase each iteration until convergence occurs (if it does!). These ideas have been used by Soewito [43], Jackson [29], Kay and probably others.

References

  1. Albert, Arthur. (1972). Regression and the Moore-Penrose Pseudoinverse. New York: Academic Press.
  2. Algazi, V. Ralph and Suk, Minsoo. (1975, December). On the Frequency Weighted Least-Square Design of Finite Duration Filters. IEEE Transactions on Circuits and Systems, 22(12), 943-953.
  3. Burrus, C. S. and Barreto, J. A. (1992, May). Least p-Power Error Design of FIR Filters. In Proceedings of the IEEE International Symposium on Circuits and Systems. (Vol. 2, pp. 545-548). ISCAS-92, San Diego, CA
  4. Barreto, J. A. and Burrus, C. S. (1994, April 19-22). Complex Approximation using Iterative Reweighted Least Squares for FIR Digital Filters. In Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing. (pp. III:545-548). IEEE ICASSP-94, Adelaide, Australia
  5. Barreto, J. A. and Burrus, C. S. (1994, November 13-16). Iterative Reweighted Least Squares and the Design of Two-Dimensional FIR Digital Filters. In Proceedings of the IEEE International Conference on Image Processing. (Vol. I, pp. I:775-779). IEEE ICIP-94, Austin, Texas
  6. Burrus, C. S. and Barreto, J. A. and Selesnick, I. W. (1992, September 13-16). Reweighted Least Squares Design of FIR Filters. In Paper Summaries for the IEEE Signal Processing Society's Fifth DSP Workshop. (p. 3.1.1). Starved Rock Lodge, Utica, IL
  7. Burrus, C. S. and Barreto, J. A. and Selesnick, I. W. (1994, November). Iterative Reweighted Least Squares Design of FIR Filters. IEEE Transactions on Signal Processing, 42(11), 2926-2936.
  8. Burrus, C. S. (2012). Prony, Pade, and Linear Prediction for the Time and Frequency Domain Design of IIR Digital Filters and Parameter Identification. Connexions: http://cnx.org/content/m45121/latest/.
  9. Bani, Mohamed S. and Chalmers, Bruce L. (1984). Best Approximation in via Iterative Hilbert Space Procedures. Journal of Approximation Theory, 42, 173-180.
  10. Ben-Israel, Adi and Greville, T. N. E. (1974). Generalized Inverses: Theory and Applications. [Second edition, Springer, 2003]. New York: Wiley and Sons.
  11. Bjorck, Ake. (1996). Numerical Methods for Least Squares Problems. Philadelphia: Blaisdell, Dover, SIAM.
  12. Byrd, Richard H. and Pyne, David A. (1979, June). Convergence of the Iteratively Reweighted Least Squares Algorithm for Robust Regression. (313). Technical report. Dept. of Mathematical Sciences, The Johns Hopkins University.
  13. Burrus, C. Sidney. (2008). Digital Signal Processing and Digital Filter Design. [http://cnx.org/content/col10598/latest/]. Connexions, cnx.org.
  14. Burrus, C. S. (1994, 2012). Vector Space Methods in Signal and System Theory. [also in Connexions: http://cnx.org/content/col10636/latest/]. Unpublished notes. Houston, TX: ECE Dept., Rice University.
  15. Burrus, C. Sidney. (1998, September 8-11). Constrained Least Squares Design of FIR Filters using Iterative Reweighted Least Squares. In Proceedings of EUSIPCO-98. (pp. 281-282). Rhodes, Greece
  16. Burrus, C. Sidney. (1998, August 9-12). Convergence of Constrained Optimal Design of FIR Filters using Iterative Reweighted Least Squares. In Proceedings of the IEEE DSP Workshop - 1998. [paper #113]. Bryce Canyon, Utah
  17. Chi, Chong-Yung and Chiou, Shyu-Li. (1992, May). A New Self-Initiated WLS Approximation Method for the Design of Two-dimensional Equiripple FIR Digital Filters. In Proceedings of the IEEE International Symposium on Circuits and Systems. (pp. 1436-1439). San Diego, CA
  18. Chalmers, B. L. and Egger, A. G. and Taylor, G. D. (1983). Convex Approximation. Journal of Approximation Theory, 37, 326-334.
  19. Cheney, E. W. (1966). Introduction to Approximation Theory. [Second edition, AMS Chelsea, 2000]. New York: McGraw-Hill.
  20. Chit, Nassim N. and Mason, John S. (1991, January). Complex Chebyshev Approximation for FIR Digital Filters. IEEE Transactions on Signal Processing, 39(1), 49-54.
  21. Daubechies, Ingrid and DeVore, Ronald and Fornasier, Massimo and Gunturk, C. Sinan. (2010, January). Iteratively Reweighted Least Squares Minimization for Sparse Recovery. Communications on Pure and Applied Mathematics, 63(1), 1-38.
  22. Donoho, David L. (2006, June). For Most Large Underdetermined Systems of Linear Equations the Minimal L_1-norm Solution is also the Sparsest Solution. [http://stats.stanford.edu/~donoho/Reports/2004/L1L0EquivCorrected.pdf]. Communications on Pure and Applied Mathematics, 59(6), 797-829.
  23. de Queiroz Cobra, Daniel Tavora. (1986, January). FIR Digital Filter Design by the Method of Successive Projections. Masters thesis. MIT.
  24. Ekblom, Hakan. (1973). Calculation of Linear Best L_p-Approximations. BIT, 13(3), 292-300.
  25. Fletcher, R. and Grant, J. A. and Hebden, M. D. (1971). The Calculation of Linear Best Approximations. Computer Journal, 14, 276-279.
  26. Fisher, John D. (1973). Design of Finite Impulse Response Digital Filters. Ph. D. Thesis. Rice University.
  27. Fletcher, R. (1987). Practical Methods of Optimization. (Second). New York: John Wiley & Sons.
  28. Gorodnitsky, Irina F. and Rao, Bhaskar D. (1997, March). Sparse Signal Reconstruction from Limited Data using FOCUSS: a Re-weighted Minimum Norm Algorithm. IEEE Transactions on Signal Processing, 45(3),
  29. Jackson, Leland B. (2008). A Frequency-Domain Steiglitz-McBride Method for Least-Squares IIR Filter Design, ARMA Modeling, and Periodogram Smoothing. IEEE Signal Processing Letters, 15(8), 49-52.
  30. Kahng, S. W. (1972, April). Best Approximation. Mathematics of Computation, 26(118), 505-508.
  31. Karlovitz, L. A. (1970). Construction of Nearest Points in the L_p, p even, and L_infty norms. I. Journal of Approximation Theory, 3, 123-127.
  32. Lawson, C. L. (1961). Contribution to the Theory of Linear Least Maximum Approximations. Ph. D. Thesis. University of California at Los Angeles.
  33. Li, Yuying. (1991, June). A Globally Convergent Method for Problems. (TR 91-1212). Technical report. Ithaca, NY 14853-7501: Computer Science Department, Cornell University.
  34. Lim, Y. C. and Lee, J. -H. and Chen, C. K. and Yang, R. -H. (1992, March). A Weighted Least Squares Algorithm for Quasi-Equripple FIR and IIR Digital Filter Design. IEEE Transactions on Signal Processing, 40(3), 551-558.
  35. Mason, J. S. and Chit, N. N. (1987). New Approach to the Design of FIR Digital Filters. IEE Proceedings, Part G, 134(4), 167-180.
  36. Merle, G. and Spaeth, H. (1974). Computational Experiences with Discrete L_p-Approximation. Computing, 12, 315-321.
  37. Osborne, M. R. (1985). Finite Algorithms in Optimization and Data Analysis. New York: Wiley.
  38. Parks, T. W. and Burrus, C. S. (1987). Digital Filter Design. [most is in Connexions: http://cnx.org/content/col10598/latest/]. New York: John Wiley & Sons.
  39. Powell, M. J. D. (1981). Approximation Theory and Methods. Cambridge, England: Cambridge University Press.
  40. Rice, J. R. (1969). The Approximation of Functions. (Vol. 2). Reading, MA: Addison-Wesley.
  41. Ruzinsky, S. A. and Olsen, E. T. (1989, February). L_1 and L_infty Minimization Via a Variant of Karmarkar's Algorithm. IEEE Transactions on ASSP, 37(2), 245-253.
  42. Rice, John R. and Usow, Karl H. (1968). The Lawson Algorithm and Extensions. Math. Comp., 22, 118-127.
  43. Soewito, Atmadji W. (1990). Least Squares Digital Filter Design in the Frequency Domain. [At: http://scholarship.rice.edu/handle/1911/16483]. Ph. D. Thesis. Rice University.
  44. Stonick, Virginia L. and Alexander, S. T. (1991, Feburary). A Relationship Between the Recursive Least Squares Update and Homotopy Continuation Methods. IEEE Transactions on Signal Processing, 39(2), 530-532.
  45. Stonick, Virginia L. and Alexander, S. T. (1992, September). Globally Optimal Rational Approximation Using Homotopy Continuation Methods. IEEE Transactions on Signal Processing, 40(9), 2358-2361.
  46. Selesnick, Ivan W. (2009). Least Squares Solutions to Linear System of Equations. [to be published in Connexions].
  47. Sieradski, Allan J. (1992). An Introduction to Topology and Homotopy. Boston: PWS-Kent.
  48. Stone, Richard E. and Tovey, Craig A. (1991, June). The Simplex and Projective Scaling Algorithms as Iteratively Reweighted Least Squares Methods. SIAM Review, 33(2), 220-237.
  49. Strang, Gilbert. (1986). Introduction to Applied Mathematics. Wellesley, MA: Wellesley-Cambridge Press.
  50. Schroeder, Jim and Yarlagadda, Rao and Hershey, John. (1991, August). Normed Minimization with Applications to Linear Predictive Modeling for Sinusoidal Frequency Estimation. Signal Processing, 24(2), 193-216.
  51. Tseng, Ching-Yih and Griffiths, Lloyd J. (1992, November). A Simple Algorithm to Achieve Desired Patterns for Arbitrary Arrays. IEEE Transaction on Signal Processing, 40(11), 2737-2746.
  52. Tseng, Ching-Yih. (1992, May). A Numerical Algorithm for Complex Chebyshev FIR Filter Design. In Proceedings of the IEEE International Symposium on Circuits and Systems. (Vol. 3, pp. 549-552). San Diego, CA
  53. Usow, Karl H. (1967). On Approximation 1: Computation for Continuous Functions and Continuous Dependence. SIAM Journal on Numerical Analysis, 4(1), 70-88.
  54. Vargas, Ricardo Arturo. (2008, May). Iterative Design of Digital Filters. [in Connexions: http://cnx.org/content/col11383/latest/]. Ph. D. Thesis. Rice University, ECE Department, Houston, TX 77251.
  55. Vargas, Ricardo and Burrus, C. Sidney. (2012). Iterative Design of Digital Filters. [arXiv:1207.4526v1 [cs.IT] July 19, 2012]. arXiv.
  56. Vargas, Ricardo A. and Burrus, C. Sidney. (1999, March 14-19). Adaptive Iterataive Reweighted Least Squares Design of Filters. In Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing. (Vol. III). IEEE ICASSP-99, Phoenix
  57. Watson, G. A. (1981). An Algorithm for Linear Approximation of Continuous Functions. IMA Journal of Numerical Analysis, 1, 157-167.
  58. Watson, G. A. (1988, October). Convex Approximation. Journal of Approximation Theory, 55(1), 1-11.
  59. Yagle, Andrew E. (2008). Non-Iterative Reweighted-Norm Least-Squares Local Minimization for Sparse Solutions to Underdetermined Linear Systems of Equations. [preprint at http://web.eecs.umich.edu/~aey/sparse/sparse11.pdf].
  60. Yu, Wen-Shyong and Fong, I-Kong and Chang, Kuang-Chiung. (1992, August). An L_1 Approximation Based Method for Synthesizing {FIR} Filters. IEEE Transactions on Circuits and Systems II, 39(8), 578-561.

Content actions

Download module as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Add module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks