Tuesday, May 22, 2012

Running Least Squares

or "Incremental Least Squares"

If you want to find the Least Squares solution to a linear algebra problem (\(\textbf{A} \vec{y} = \vec{b}\)), you probably would use the formula

$$\hat{y} = (\textbf{A}^\intercal \textbf{A})^{-1} \textbf{A}^\intercal \vec{b},$$

where \(\hat{y}\) is the closest possible value to \(y\). If you need to do this for many points, the operation could become expensive, both in time and memory. What you instead could do is this:

Imagine you have calculated the approximation for some number of samples. You had \(\textbf{A}\), \(\vec{b}\) and \(\vec{y}\), and calculated \(\hat{y}\).

Now you want to add another point to the calculations. Instead of recalculating the transpose, inverse and multiplications, you can add one more row to the formula.

$$\hat{y}' = \left( \begin{bmatrix}\textbf{A} \\ \vec{r}^\intercal\end{bmatrix}^\intercal \begin{bmatrix}\textbf{A} \\ \vec{r}^\intercal\end{bmatrix} \right)^{-1} \begin{bmatrix}\textbf{A} \\ \vec{r}^\intercal\end{bmatrix}^\intercal \begin{bmatrix}\vec{b} \\ z\end{bmatrix}$$ which expands into $$\hat{y}' = \left( \textbf{A}^\intercal \textbf{A} + \vec{r} \vec{r}^\intercal \right)^{-1} \left( \textbf{A}^\intercal \vec{b} + \vec{r} z \right)$$

Here \(\vec{r}\) is a vector of the input variables (e.g. \(\begin{bmatrix}x \\ y\end {bmatrix}\)), and \(z\) is the new target.

You might now see where this is going.

  • All you need to keep in memory, are the matrix \(\textbf{M} = \textbf{A}^\intercal \textbf{A}\) and vector \( \vec{v} = \textbf{A}^\intercal \vec{b} \).
  • Whenever you want to add another point, you increment \(\textbf{M}\) with \(\vec{r} \vec{r}^\intercal\), and \(\vec{v}\) with \(\vec{r} z\).
  • When you want to get the result, you calculate \(\hat{y} = \textbf{M}^{-1} \vec{v}\). This operation will require at least two samples.
  • \(\textbf{M}\) and \(\vec{v}\) both start off with only zero-entries.

The size of \(\textbf{M}\) is \(n \times n\), and \(\vec{v}\) is \(n\), where \(n\) is the number of coefficients in the system (the width of the matrix \(\textbf{A}\).

Sunday, March 18, 2012

Android Binary XML

I have created a library for parsing the binary XML-files that is created inside Android APK files.
var reader = new AndroidXmlReader(stream);  
var doc = XDocument.Load(reader);  
To download the source code, visit: androidxmldotnet.codeplex.com

Sunday, October 2, 2011

Printing GS1 DataMatrix with ZPL

GS1 is a standard for encoding information in barcodes. It can be used to label products in a warehouse, or when shipping the products to customers. A GS1 code consists of a number of pre-defined fields, such as item number or product type.

The format is relatively simple. Each field is prefixed by a decimal number called the Application Identifier (AI for short). The length of the number depends on the first two digits (e.g. 250 begins with '25', so the length must be 3 digits). After the label, comes the data. Depending on the field number, the field can be either fixed-length or variable-length. The variable fields also have a maximum length, but must be suffixed by a special character: ASCII 29 (Group Separator, GS for short).

Some barcode formats only allow fixed-length fields, because they cannot encode the GS character. I will only talk about DataMatrix codes, which can support any 8-bit code. A GS1 DataMatrix code starts off with the meta-character FNC1. More on this later.

DataMatrix comes in a few different quality levels: 0, 50, 80, 100, 140 and 200. These numbers stand for the amount of data that is added to the symbol for error correction. 0 use no error correction. 50 to 140 use convolution encoding. 200 use Reed-Solomon encoding. These quality levels are also referred to with a ECC prefix: ECC 50 to ECC 200. The GS1 standard recommends using only ECC 200, and it is the one I will be talking about here.

ZPL is one of the languages that can be used to talk to your Zebra label printer. It is mainly text-based, and consists of a large number of cryptic commands. Each command begins with ^ or ~ (These characters can also be customized). Then comes one or two uppercase letters specifying the name of the command. Last comes zero or more comma-separated arguments.

Each document begins with ^XA (Start Format) and ends with ^XZ (End Format). In between you can change almost any setting, issue print commands, and even flash a new ROM. I will mostly discuss the ^BX command, which print DataMatrix barcodes.

^BX can take up to 7 arguments:
orientation, height, quality, columns, rows, format, escape character. Quality should be 200 for ECC 200, and you want to set some escape character. Here is the command I used:
To specify the data, you should follow the ^BX command with a ^FD...^FS region. Inside this region, you can enter almost any data, but you might want to stay with simple ASCII characters. You can use the following escape sequences to encode other characters:
  • @1 to @3 - FNC1 to FNC3. These are meta characters that lies outside the normal data-range.
  • @5NNN - codepage. Changes to codepage NNN (three digit decimal number).
  • @dNNN - character. Inserts data character NNN (three digit decimal number).
  • @@ - escaped. Inserts the escape character itself.
To encode the GS1 string (90)SE000(250)1234567890 as a DataMatirx barcode you could write:
Of course, you would need to specify a few settings before hand. You could get a template to work with by using the program Zebra Designer that comes with the printer. You just design your label, and print it to a file. (File → Print → Print to file)

For more information: