2010-11-27

Filter design (2)

Input actual data

Let's input some signal to the filter that we designed last time. Table 1 shows the input of constant signal. Constant signal will be boring, but, We start with a simple one.

Table 1 Constant input


To make sure, I will show you how to compute the Table 1's red output. Here y_n and n=1,
In this case, the filter gets the first three inputs. The inputs are all the same (= 1), therefore all the outputs are also the same. Let's compute the transfer function. We compute all the time the transfer function in digital filter.
What, Jojo, You! Be surprised. (it's a bit old and does anybody know Jojo's strange adventure by Araki Hirohiko?) The ratio of input and output is equal to the transfer function!
Here is a small details. In the Table, y_n has a value at n=0,8 since we can compute the cos value. But there usually is no n=-1 value in the real data acquisition (If we start with n=0, then no data at n=-1). Therefore, it is also possible to say there is no output value at y_0.

I think this example is a bit boring since input is constant and thus
the output is also constant. The followings are dynamic examples in
Table 2 and 3.

Table 2 cos π/3 input

Table 3 cos 2π/3 input


Let me show you how to compute the red output in Table 2.
The transfer function is the following.
Transfer function represents that how much input is transfered to the output. Here the value is 1, this means, the input and output are the same. The signal of this frequency go through this filter without change.  You can clearly see the correspondence of the input and the output, they are the same. Transfer function is great.  In the case of Table 3,

The transfer of this is:

Needless to say, this frequency can not pass this filter.

Conclusion

The mathematics used in here is not so complex. If you can accept the Euler's equation, the high school math can handle the rest of them. You can Euler's equation is also explained by (infinite) series expansion of e^x, sin(x), cos(x), then you can compare the sin(x), cos(x) and e^x. This gives you a hint of relationship between them. At least one can see some kind of relationship, I presume.

The transfer function is an eigenvalue of the sampling filter function. These are ideal cases, but it is fun to see the theory works pretty well.

Filter design (1)

This is about filter design of Hamming's digital filter. The chapter 3.9 is outstanding, so I would like to make a note.

While ago there was a soccer game. How to suppress the Vuvuzela sound (but other sounds should pass) was a popular topic at that time. In this case, you analyze the frequency of Vuvuzela sound and design a filter which doesn't pass that frequency. The design of digital filter is: which frequency of the signal will be passed and which frequency of the signal will not be passed.

See the following article for instance, http://blogs.mathworks.com/loren/2010/06/30/vuvuzela-denoising-with-parametric-equalizers/

In chapter 3.9, a simple non recursive filter design is described as an example.

The filter looks like the following.
This filter uses three samples. The design of filter is to determine the a,b to fit to your desire. First, we will calculate the transfer function of this filter. As I explained in a former blog post, a transfer function is an eigenvalue of the filter function. Thus, it shows the output of the input of filter F. Here the input signal x (this is a function of time t, x(t)) and the filter function is F, then the eigenvalue λ is F x = λ x. If you are familiar with linear algebra, you can consider the F as a matrix A, a scalar λ, then you will see that is the same as A x = λ x. Now we compute the transfer function:
Therefore, transfer function is
If you want to make your filter passing the π/3 frequency (=1) and you want to cut 2π/3 frequency (=0), we set this transfer function under that condition.
By solving the system, we get

The filter is:

We design a digital filter, but, it is still not clear what this is. So, next time, I will input the actual signal into this filter and see how this filter works.

2010-11-24

Introduction to Linear Algebra: Projection and a Simple Kalman Filter (3)

Simple Kalman filter

In a sense, Kalman filter can predict a near future from the past and current condition. (Maybe this is a bit too much to say, there are of course only some extent and limitations.) Let's write it in a eqation.

 x_{new} = x_{old} + f(x_{current})

This means that the future is somewhat the extension of previous state with a modification, and the modification is now hidden in the function f. OK, I am not an expert about Kalman filter, so, I will write down only a simple one that I could handle.

In a simple Kalman filter, x_{new} is predicted by past x_i-s. The past data span a subspace of the data and the new value is just the best projection onto the past subspace. That how I understand it. (This might be wrong.) In the Strang's book, an interesting computation method is explained, but, it is just a sketch. Here I will write the overview of the idea of Strang's book.

First, I need a preparation about 1/k.
Therefore,
We saw the last two blog entries that the best expectation of sequence of the data is the average in the sense of least square. Using the above equation, I will rewrite the average equation. You will say why? I will explain the reason shortly.
Now I have enough materials to explain what I want to do. We have a sequence of data from i = 1 to n. We will have more data n+1, n+2, ... later. But, if we need to compute all the history of the data to predict the near future, this is not so good. Because, the time passed, we need linearly more computation. What we need is some summary of history state and the current state, then using these two states, we compute the best next state (the best is in the least square sense). If we could do that, the computation cost is always the same, this is nice for a realtime system. It just return to the x_{new} = x_{old} + f(x_{current}), we want to know the near future by old and current states. Therefore, we made a equation that has n and n-1 (please see the equation again, you see (i=1 to n-1) + n.) Here, \frac{1}{n-1} \sum_{i=1}^{n-1} x_i is the average of the past, so I rewrite this as x_{old}.
Now you see this is the best prediction in the least square sense with the history of the last step and the current state. This is Wow.

This three articles, we saw the least square from two point of views: calculus (analysis) and linear algebra. They are the same. We also see its application, Kalman filter.

2010-11-23

Introduction to Linear Algebra: Projection and a Simple Kalman Filter (2)

Linear algebra way

In the linear algebra way, the best x is a projection of right hand side onto the column space of the matrix. Because the solution is only possible in the A's column space (means the solution is only represented by the A's column vector's linear combination), the best solution is the projection of b onto the column space. Figure 1 shows the geometric interpretation. The matrix A and b are:

Here A is a vector, so the projected best x is:

The result is the same to the calculus way. This is also the average. (If you are not familiar with projection matrix, see the Figure 1. In the Figure, e is perpendicular with A, i.e., A^T e = 0. You can derive it from here.)
Figure 1. Project b to A's column space

My interest is why these are the same. Minimization of quadric is a calculus (analysis) problem, and projection is more a geometric problem. Is this just a coincidence? Of course not. They have the same purpose.

As in Figure 1, projection is the minimal distance between b and A's column space. The distance is square root of squared sum in the Euclidean space (Pythagoras's theorem). Minimizing it is the same to the calculus way, though, the idea and how to compute it looks different.

Once I wrote the following, I like Keigo Higashino's books. One of his book, ``Yougisha X no Kenshin'', describes about deceiving a problem makes wrong conclusion. The example is mathematics, if you deceive someone as this is a calculus problem, but actually it is a geometry problem, one can not reach the correct answer. A clever guy deceive the police by putting an wrong answer, that's a fun detective story. Higashino's book usually describes science quite well, though, I have a question on this point. I found interesting that when the problem setting is the same, even different approcaches can conclude the same result in mathematics. I feel this more and more when I study mathematics more. I am surprised when the different looking problems are originated from the same idea. It looks like climbing a mountain. When I was at the sea level, I can only see some of the views from specific directions only, these views look different, however, once I see the overview from the mountain, they are just the same view from different positions. Studying mathematics is like to have a map. Some of the roads seems not connected, but if I have a map, I can see actually they are connected. I think all the roads are somewhat connected. If I could not see, that means I need to study more.

Here we found the closest vector from a vector by

  • calculus: minimize the error
  • linear algebra: projection.

Next time, I would like to talk about Kalman filter. Kalman filter estimates a near future based on observed data that have some noise. The basic idea to predict near future is the same as mentioned in this blog. But I recently happen to know it has one interesting aspect and I would like to explain that.

2010-11-21

Introduction to Linear Algebra: Projection and a Simple Kalman Filter (1)

Introduction about linear algebra, calculus, and a simple Kalman filter

I found interesting that the relationship among linear algebra, calculus, and a simple Kalman filter. So I will make a memo about this.

Problem

Given a simple observed data sequence (x_i), we can assume these are equally plausible and we can apply the least square method. In this simple setting, the outcome is just an average. You can find this topic in Gilbert Strang's an Introduction to Linear Algebra, chapter 4.2.

For example, the observed data is [70 80 120]^T, if these are equally plausible,

 x = 70
 x = 80
 x = 120.

These euqations are strange. They look like, x is 70 and 80 and 120, simultaneously. Here, these are observed data, so they have some errors. But actually we observe the same data. The motivation is to find the best possible data we could  have from the observations.

Therefore, the system is:
There is no such x that satisfies the system. But, let us think about what is the best x.

Calculus way

We could use an idea from calculus to find the best x. The idea is: the observation has errors and what kind of x can minimize the error. This is called Gauss's least square method. First, we compute the squared error (E). This is also in the Strang's book.

 E = (x-70)^2 + (x-80)^2 + (x-120)

E is x^2's equation, therefore this is parabola. That means we can find a minimal point. Such point has 0 tangent, therefore, we could find it with
Let's compute this.

You can see this is actually an average. The best x is  an average, this fits my intuition. However, I did not think about why average is the best in what kind of sense. In this case, variance is relatively small, then, my intuition works. However, if the variance becomes larger, my intuition stops working. I once wrote about this in my blog ``A 6σ Woman.'' Average is the best here in the least square sense.

Next, let's find the best x with linear algebra way.

2010-11-13

ifgi tracer: report 2010-11-12

I am slowly working on my small hobby project: ifgi tracer.
Currently, I can load an obj file and rotate with trackball operation it in the window. So far, it is still OpenGL only. No light, No Zoom, No translation, no shading.... But, at least I don't have Gimbal lock. The source code is publically available, though, at this point, there is no value at all. But, I would like to have some fun on this project.


2010-11-06

Eigenvalue and transfer function (8)

Last time I use sin and cos, but this relationship becomes simpler if we use Euler's formula.
Let's apply the same operator T.
Wow again. This is also eigenfunction of operator T.

This function is based on trigonometric functions. Therefore, we use these trigonometric function as the basis of the frequency domain analysis. Eigenvalues show us a brief overview of the operation and its function.

Assume we have an input x and an output y, operator T is applied to the input x, then the result is the y. If eigenvalue exists, we could write it as the following.
This means, the input is transfered to the output and how much transfered is λ. Therefore, signal processing people call this λ as a transfer function. Why it is called function? λ looks like a constant. Usually, λ is not a function of input x, but it usually has some parameter, means this is a function. For example, in the former equation, λ is not a function of x, but a function of ω.  In signal processing, x is usually time t and ω is frequency.

This means, a transfer function in signal processing is eigenvalue of linear algebra. How great it is!

This is an overview of recently I understand about eigenvalue, eigenvector, eigenfunction, and transfer function. I hope this also helps someone.

Acknowledgements

I wrote this article, but, actually first one month I didn't understand this at all. I thank Alexander B. who is so patient and answered my stupid and similar questions every time.

2010-11-05

Eigenvalue and transfer function (7)

Eigenvalue and transfer function

In the Hamming's book, he repeats to mention about the merit of using trigonometric function as a basis in signal processing. Unfortunately, that is not the main point of this blog, therefore, I could not compare it with the other bases. I will just stick to this basis with assuming this is a good one. Let's see the eigenvalue of trigonometric function according to the example of Hamming's book. The first example in his book is
 A sin x + B cos x.
We apply a transformation operation. Then, let's see something is changed or not. If something doesn't change, it will be a eigenvector and we will also see its eigenvalue.

Transform T is a shift operation of the origin of coordinate like T: x → x' + h. Why someone wants to shift the coordinate? For example, signal processing usually doesn't matter when you start to measure the signal sequence. When you started to measure the signal, then, that point is the origin. Usually there is no absolute origin of time. If you want to re-set the time domain, that would be also convenient. The question is what kind of property doesn't change by transform operation. Let's apply this transform operation to the trigonometric function.

where,
A', B' are constants that is independent from x. Wow, after the transformation, the function became the almost the same form. It is a linear combination of sin x and  cos x again.
At the end, this operation has the same form of
A' and  B' looks like eigenvalues and sin and cos looks like eigenvector. (eigenfunction)

I found this point of view is fantastic. How do you think?

Once I was scared my friends talk about eigenfunction, since I don't know what it is. But, you also are not scared this anymore!

2010-11-04

Eigenvalue and transfer function (6)

Eigenvalue and Eigenvector

Function case

Interestingly, the same story is repeated again in function. (Well, ``interesting'' is just my personal feeling. So, many might not agree with this. I found this --- the same story repeated again, but in the different level --- interesting in mathematics. Like Hitchhiker's Guide to the galaxy's jokes have some mathematical structure.) So far, we apply an ``operation'' to a scalar or a vector. Then, we again apply an operation to a function. We want to know what is the substance of the ``operation'' instead of the each result of operation. We could not know the substance at once, but we could know the response of the function with an operation.

Usually, a function is an operation to a scalar or a vector, therefore, it is a bit confusing to think about an operation on an operation. Let's see an example. Let's assume a function f and a scalar or a vector x, this function f can be an operation on x, we write this as y = f(x). Also assume a function g that can operate on f, y' = g(f(x)). This is the meaning of an operation on an operation. Here, interesting matter is what is g of f. We are not so interested in that which x is applied. OK, interesting is subjective matter, so I would like to explain a bit more. For example, assume a noise reduction function f, we want to improve a bit more with a function g. Then, what is the combined noise reduction filter g ・ f? This is usually an interesting question and usually a specific input signal x is not so interesting for a filter design. Because, we are usually interested in a filter that always works, instead of the response of a special input.

We could write down like this:
operator g ・ f = y
If this becomes
operator g ・ f' = λ f',
we can see an aspect of this operator g. This f' is an eigenfunction. λ is still called an eigenvalue.

2010-11-03

Eigenvalue and transfer function (5)

Eigenvalue and Eigenvector

Vector case

Next, let's think about vector. I assume the readers know about matrix multiplication a bit. When a matrix applies to a vector, then this generates a new vector. For example, a matrix can rotate a vector, or enlarge/shrink a vector. We say we can apply a matrix A to a vector x. The matrix A could be a rotation operation, or any. The result of application creates a new vector b.

 Ax=b

If you see this, it looks like scalar's multiplication. But, usually A is quite complex and hard to understand what it is. But if there is a scalar λ and a vector x', such that

 A x' = λ x'.

This means:
We can replace a complex matrix A with a scalar value λ. 
I think this sentence has the whole idea of this topic. Usually it is not possible to find such λ for any vector. But, we have a chance to find a specific x' and its relating a scalar value λ.

When I saw this, I said, ``Wow.'' This is a powerful idea. If I see a 100x100 matrix, I have no idea what this matrix does unless it has a very specific form (e.g., I can tell what an identity matrix does). But, if we could find this pair, a matrix A multiplies the vector x' λ times.

Here, A does something on a vector. For instance, it could be a rotation, a transformation, a magnification. The substance of the matrix is in the λ and x'. These λ and x' are called the substance or property of the matrix: eigenvalue λ and eigenvector x'.

Now you see why mathematicians think about eigenvalues and eigenvectors. A matrix A is usually so complex and nobody can understand it. But, if we can find a simpler form, scalar multiplication, we can see ``an aspect'' of A. This is called eigenanalysis.

By the way, one n by n matrix A (n>1) has usually many eigenvalues and eigenvectors. If we could always have one eigenvalue and one eigenvector for a huge matrix, it sounds simple, but, the world is not so easy. Please note that there are many eigenvalues for one matrix, therefore, I use ``an aspect'' of a matrix.

Eigenvalue and transfer function (4)

Eigenvalue and Eigenvector

Scalar case

Let's start with multiplication of scalars.

3 x 4 = 12

If I could use variables a,x,b:

ax = b.

The first example shows x=4 times a=3 equals b =12. Here, I multiply x a times. I didn't multiply a times x. In the scalar case, these have no difference since the following commutative law works on scalars.

ax = xa

Please note, this is not always correct. Even we can not exchange the meaning in the scalar numbers. For example, assume there is a chocolate box that costs five Euro. We can buy two packages. This is 2 times 5 = 10 Euro. This is not two's 5 Euro time. We can double the 5 Euro chocolate, but we can not see five Euro time doubles. Usually it doesn't make sense: five Euro times (five times works, five Euro times has a problem). So I remind the order of operator is also important since vector is more strict about the operations.

2010-11-02

Effective STL

For long time, I know I should read this book. This time finally I read Effective STL by Scott Meyers. Allocator is way to difficult for me, but others, like usage of remove() and erase(), algorithm's topics are quite interesting and useful. Highly recommended.

Eigenvalue and transfer function (3)

Function

Here I want to put matrix according to the order of this story, however, I will skip the matrix story for simplicity.

Vector is a sequence of scalars. The sequence order of scalars is very important. If we changed the order of scalars, they are totally different vectors. For example, we had a vector that represents position, it was [direction distance] that means 50 degree from north, distance 5 km. If we exchange the direction and distance, it becomes [distance direction] that means 5 degree from north, 50 km distance. That is the different position (at least in the Euclidean space).

If we can put 4 scalars. Figure 1's the second from the top shows the vector that has 4 scalars. A scalar is one (real) number and a vector is a sequence of scalars. If we add more scalars in a vector, what happens? If we add scalars more and more, infinite number of scalars are added, then it becomes a function as shown in the Figure. OK, I cheated here a bit. We need some more prerequisite to make a function from a vector. However, I think this is a good intuition. (We can detour a bit here about this intuition. Some mathematics book wrote about 'inner product of functions', this is strange, how can we have inner product of functions. But, if we can follow this intuition, a function is a extension of a vector, we can see the inner product of functions. A correlation coefficient is also a inner product, therefore, 1 is correlated, 0 is un-correlated. It is a inner product, 0 means perpendicular, then there is no relationship. This intuition gave me these understanding, so I think this is not so bad.) I hope now you see one of the relationships among scalar, vector, and function.


Figure 1: Scalar, vector, and function

If we see in this way, the difference of scalar, vector, and function is only the difference of number of pairs: X and Y.

  • Scalar: One X (e.g., height) and its value (e.g., 170cm)
  • Vector: multiple X (e.g., [angle distance]) and its values (e.g., [50 5])
  • Function: continuous X and its value Y (e.g., Y = f(X))

Now, what is invariant of scalar, vector, and function? This kind of abstraction is common in mathematics. Why we care such invariant? Because it could be the substance of the object. Also if something does not change, then, we don't need to distinguish them. That's great we have not so much time, so we can skip to distinguish them. We are not so interested in masks, we want to know the real face under the masks. Masks can be changed, but, the real face can not be changed. Something does not change under many conditions, it could be the real face -- substance. Therefore, we want to know the invariant. Eigenvalue and transfer function need this abstraction, so I first talked about this.

Next, let's talk about eigenvalue.