Lx=d: SundayResearch

Appendix A: null space and column space We use the null space for the proof, therefore, I will explain the null space a bit. If you know about the null space, of course you can skip this entry. The null space of a matrix A is a set of non-zero vector x that satisfies A x = 0 . Let me show you an example square matrix A that has null space. When x \neq 0 , following x is a solution. Therefore, this x is a null space of A . When an a  is an scalar, a x , a \neq 0 are also the solutions. It means these are also null space. In this example, the matrix is singular (and square). If the matrix is not singular, the solution must be 0 only. Because, if a square matrix is not singular, there is the inverse, Therefore, x = 0 . In this case, we say there is no null space. Let me show you another example, but this time a rectangle matrix A that has null space. The solution is the same as the last example. By the way, these are all about definition of null space. I could fin

By the way, one of my friend told me my blog is totally ununderstandable. If you share my friend's opinion, and if something I could improve, please let me know. Thanks! Explanation from Linear combination and basis transformation Let me explain this from another point of view. This explanation doesn't need null space, but, it lacks a rigorous proof. However, we have a proof by null space and so I think this is correct. For me this is a more intuitive explanation. From the independence of the columns of A , the independent vectors will be organized as the following. You can also see the how the resulting columns are computed. Since A^T is a linear operator, This becomes 0 when A^{T}  a _*  degenerates. However, this is also the same form of basis transformation. Each basis is each column. Because, A^{T} 's row are independent (since A 's column are independent, transposing A exchanges columns with rows.) Each independent row vector is projected to the each ind

Why A^{T}A has the inverse Let me explain why A^{T}A has the inverse, if the columns of A are independent. First, if a matrix is n by n, and all the columns are independent, then this is a square full rank matrix. Therefore, there is the inverse. So, the problem is when A is a m by n, rectangle matrix.  Strang's explanation is based on null space. Null space and column space are the fundamental of the linear algebra. This explanation is simple and clear. However, when I was a University student, I did not recall the explanation of the null space in my linear algebra class. Maybe I was careless. I regret that... Explanation based on null space This explanation is based on Strang's book. Column space and null space are the main characters. Let's start with this explanation. Assume  x  where x is in the null space of A .  The matrices ( A^{T} A ) and A share the null space as the following: This means, if x is in the null space of A , x is also in the null spa

We can see matrix multiplication A^{T}A frequently, for example, in the least square method. If matrix A has independent columns, this matrix has the following great properties: it is square, symmetric, and has the inverse. I am interested in why A^{T}A has this properties and would like to explain that. The explanation is based on Gilbert Strang's Introduction of Linear Algebra, 4th edition. The explanation uses null space and quadric form, it is an elegant explanation. But, if I just follow the Strang's explanation, I only need to write: see Strang book. So, I would like to add a geometric explanation. Although, I don't have a rigid proof, it is just a little bit intuitive for me. Yet, I hope you can enjoy that. Even if my explanation is bad, you can still see the Strang's explanation. Properties of A^{T}A We can see matrix multiplication A^{T}A frequently. We can see this pattern in a projection operation, least square computation (Actually, those two are the

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 i

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 eigen

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 en

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 t

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 bes

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.

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 usual

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 the