## 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);


## 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:
^BXo,h,s,c,r,f,g
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:
^BXN,7,200,,,,@
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:
^XA^BXN,7,,,,@^FD@190SE000@d0292501234567890^FS^XZ
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)