We wish to carry out the minimization described in the previous section.
The Steepest Descent technique is a standard multi-dimensional minimization that "converges only linearly to the solution, but it will usually converge even for poorr initial approximations" (Burden-Faires, p.569). In our case, we are trying to find the vector x = (b,w,a) that minimizes the energy J. We start with an initial guess x0 and iteratively update our solution x by:
The three derivatives that compose the gradient are:
For our purposes, a good initial guess for b in x0 is to threshold our given signal h, setting it 1 if greater than 0.5, 0 otherwise. Initial guesses for the constants w and a in x0 hopefully can be made based on the type of data given. As for the step size 
, we try to set this value as large as possible while still reducing the value of J. This can be done by iteratively evaluating J as described in Burden-Faires, p. 571. The value of the constant k should be determined experimentally. We used k = 0.1 N2, where N is the length of the vector b. To make sure our barcode b is between 0 and 1, at the end of each iteration we project:
The program descent.m performs steepest descent minimization on b and w for a given noisy signal h. The call is of the form "[b,w] = descent (h)". For simplicity, we assumed a = 1, but the minimization over a could be incorporated into the program if desired. The number of iterations that the program runs for can be set by changing the value of itMAX in the program. At each step, the program plots the original signal h, h vs. the convolved signal b*g, and the barcode signal b. The current iteration and value of w is reported above the bottom plot. Note the program may return negative values for w, but this should not concern us since w is squared in the Gaussian g. For example, the value of w used to generate the data h below was 0.02, but the program found w = -0.018092. The current value of J is shown below the bottom plot. The picture below shows what a run of descent.m should look like.
In the next section, we provide numerical results on test barcode signals.
 Back to Main Page |
 Next: Numerical Results |