Sampling Rate is Not Only about Pixels: How to compare the sampling rate between your camera and "single-pixel" camera

At the beginning, I'd like to make clear two terms: "Nyquist frequency" and "Nyquist rate".
Some of you may take them as the same thing, and even some textbooks did so. However, although they are quite similar, they are actually different.
Reference: http://en.wikipedia.org/wiki/Nyquist_frequency
Nyquist Frequency: A property of system. For a given system, sampling rate $f_s$ is fixed. The Nyquist frequency of the system is the allowed highest frequency of a signal that could be sampled without aliasing, which is $f_s / 2$.
Nyquist Rate: A property of signal. For a given band-limited or band-pass signal, bandwidth B is fixed. The Nyquist rate of the signal is the necessary lowest sampling frequency of a system that could sample the signal without aliasing, which is $2B$.

Then for an (imaging system, image signals), you can interpret the sampling rate is the number of pixels, the highest frequency of the image is the resolution of the image.
Then the Nyquist says here, for a imaging system, the number of pixels (sampling rate) is fixed, the highest allowed resolution of the pixel is determined by/proportional to the number of pixels. For different kinds of measure of resolution, the proportion factor differs.
Meanwhile, for an image signal, whose resolution (band-width) is fixed, the required pixels is then determined by/proportional to the resolution.

So the number of pixels is actually the number of samples a system takes for a given image.
Then does it mean "single-pixel" means the number of samples is 1? The answer is definitely no.
So how to interpret the "single"-pixel?

It's a little tricky, but still can be understood. The only thing you need to do is adding a time-axis.
The traditional imaging system in your cameras actually taking samples at one time, each sample is a pixel. So the total number of samples is (number of pixels in a unit of time) x (unit of time). Since the (unit of time) is 1 here, we usually ignore it.
For the "signal-pixel" camera, the number of samples is (number of pixels in a unit of time) x (unit of time). Here (the number of pixels in a unit of time) is 1, whereas the (unit of time) is not 1, which determines the number of samples.
Image sensors are silicon chips that capture and read light. So in traditional imaging system, we need thousands of image sensors, whereas in single pixel camera, we only use one image sensor to capture and read light.
That's the trade-off, number of pixels (image sensors) and unit of time (exposure time).

Therefore, improved interpretation of Nyquist sampling here is to consider the sampling rate being (number of pixels in a unit of time) x (unit of time), i.e., the product of space sampling and time sampling.

How to understand "Nyquist sample v.s. CS"?

In this blog, I will discuss from a communication system point of view about the Nyquist sample and CS theory. A communication system usually samples and processes a 1D signal. So here we are talk about 1D signal cases.

What does Nyquist say for 1D signal?

As shown in the figure, for a analog signal, we need to first sample it to digital signal, and then process it, and de-sample/reconstruct it into analogy signal again.
Therefore, the "process" part is called digital signal processing (DSP).
The Nyquist sampling happens in the "sampling" part, before DSP.
Then what does Nyquist say?
That is, given a signal with the highest frequency component being $f_m$. The sufficient condition for return from the digital signal $x[n]$ to $x(t)$ is that the sampling frequency $f_s$ is at least $2f_m$.
It should be noticed that this is only a sufficient, not necessary condition.
In certain cases, the condition is necessary, e.g., the signal is band-limited. If the whole limited band is occupied by the signal, or we don't know which portion of band the signal occupied, in other words, the only information we've got is the highest frequency of the signal,
(we call this kind of signal strict-sense band-limited signal), then the only way is to use Nyquist rate to sample the signal.
However, you may argue that, in practice, the signal may not band-limited, then what should we do?
The answer is making the signal band-limited before we sample it. This can be done using a LPF. And it is another story that how the band-limited signal approximates the real signal. Here we only focused on the already band-limited signal.
On the other hand, you may also ask that, if we have a band-pass signal, (of course, the band-pass signal is a band-limited signal, however, not strict sense band-limited signal), then can we have lower sampling frequency.
The answer is yes. To see the method, just think we move the band-pass signal to the base-band, and then it become a strict-sense band-limited signal. Then it is obvious how Nyquist rate works. Actually, we are given more information, i.e., the signal is band-passed from $f_L$ to $f_H$, thus we are able to sample the signal using frequency below $2f_H$.
In this case, we can call such sampling process under-sampling. However, it can be viewed as Nyquist sampling via some conversion.

• It should also be noticed that here the sampling is uniform sampling. If you are interested in this topic, you can review some references in non-uniform sampling.
• Also, when it comes to 2D signal, it is a little tricky to see the Nyquist sampling. It's beyond this blog.

What does CS say?

Before we go into CS, I'd like to a more complete communication system.
As you see in the figure, all "information" after the dash line are in format of bits stream. And if we ignore all imperfection of the system in between, e.g. we have perfect channel, perfect modulation scheme. Then the process after dash line is distortion free.
Then we move before the dash line, as we shown in last section, the sampling and de-sampling process can be distortion free.
Then how about the quantization? It brings distortion, and the precision of the quantizer determines the intensity of the distortion.
However, you can set all these asides to understand CS.

As shown in the figure, A/D converter actually is responsible for sampling and quantizationg, D/A converter does reverse things.
And source encoder is responsible for compression.
Then consider, if we can sub-sample the signal, then we may not need to compress the signal. Then the only question is how to reconstruct the signal. CS theory just asserts the signal can be recovered faithfully, if the signal is sparse in certain domain, which is highly incoherent with time domain. For instance, the frequency domain is incoherent with time domain.
The CS system can be imaging as following,

$x[n]$ is corresponding to $r[n]$, however, in the real system, we actually do not have $x[n]$. Instead, we have already compressed $p[n]$, which corresponds to $s[n]$.
From $r[n]$ to $r(t)$ is not a problem. Then how to get $r[n]$ from $s[n]$? That's where CS works.
And as you can see, the A/D (D/A) converter becomes A/I (I/A) converter.
The sampling requirement reduced, while the reconstruction is more powerful. This is another kind of asymmetry compared to traditional "source encoding".

How can CS be more powerful?
Say, what if the signal is sparse in time domain, or in a domain coherent with time domain? Then, according to the CS theory, we should not under-sample in time domain as shown before. We need to under-sample in a domain incoherent with the sparsity domain.
Then how to design it? The most beautiful part of CS is RIP. The RIP says if you design the "compression" part as under-sampling signal in a domain, while the under-sampled part of the domain satisfies RIP, then the signal can be reconstructed faithfully.
To my understanding, (and certainly you can have your own interpretation), a matrix satisfies RIP essentially is a subset of domain, i.e., only a few of basis of the domain, while the domain is incoherent with almost every other domain. That's the "university" of CS theory.
An example is Gaussian matrix, which is almost incoherent with either time domain or frequency domain.
It is a little tricky, but if you take into account the role of "overwhelming probability", it would be easier to understand the inner connection.
I didn't go into the mathematical part of these relationships. But if you look at them as a black box, such interpretation does help.

Then the problem is how to first transform the signal into $\Phi$ domain, to make the following under-sampling possible.
This is the story of A/I converter. I won't go into this topic. But intuitively speaking, it takes the help of convolution/integrator.

And again, for 2D signals, like imaging system, even high-dimensional signals, the Nyquist sample and CS can be interpreted in another way. And a most vivid example is the "single-pixel camera".
I will discuss the 2D signal sampling, especially the imaging systems, in future.

Sparse Representation, Compressed Sensing, Single Measurement Vector, Multiple Measurement Vector: connections and differences

Purpose of this blog entry

Sparse representation (SR), compressed sensing (CS), single measurement vector (SMV),  multiple measurement vector (MMV), I was ever confused about these terms. They seems to be the same, however, the way they using to describe problems differs.In this blog, I aim to make clear the inner relationship among them, and the development of these theories.

The Big Picture

To my understanding, the following figure describes the relationship of them. 
To see the inherent relationship, I'd rather like to break the CS into two kinds, 1st generation CS (CS1G) and 2nd generation CS (CS2G). The difference will be discussed later. Nevertheless, such notation is not used in current society. So please not be confused when reading papers.
In the paper, CS is referred to CS2G. And SMV is referred to CS1G.
The notion SMV is first mentioned in [10]. (And in [11], one measurement vectors is used to describe the SMV problem).
We will return to the big picture in the end of this blog.

SMV: SR and CS1G

The SMV model basically presents such problem: $y = \Phi x$

•  sparse representation: $y$ is viewed as a signal in reality, $\Phi$ is called an over-complete dictionary, $x$ is the sparse representation
•  we want to find a sparse representation of the signal using a dictionary, and we want the signal to be as sparse as possible
•  $\Phi \in R^{M \times N}$: if M < N, the dictionary is over-complete, if M = N, the dictionary is complete, if M > N, the dictionary is under-complete. The "complete" is viewed from the signal $y$. Simply speaking, if the length of the representation is larger than that of the signal, then the signal is "over-represented", and thus the dictionary is "over-complete".
•  2D DCT, DFT, etc., are sparse representation of the signal using a complete dictionary
•  In this blog, we consider sparse representation of the signal using an over-complete dictionary
• 1st generation compressed sensing:  $x$ is a sparse signal in itself, i.e., there are only a few non-zero entries in $x$, $\Phi$ is called measurement matrix, $y$ is called measurements
• we want to sample a sparse signal using less measurements than its length, in other words, compressing the signal.
• here we only want $\Phi$ to be over-complete in terms of $y$
• note that "$x$ is a sparse signal in itself " is the identity of CS1G. For CS2G, as we will discussed in next section, $x$ is a sparse signal in domain $\Psi$, which is a generation of CS1G

Therefore, SMV is actually a model of SR and CS1G, with each describes different applications.
And we can also view SR as the reconstruction step of CS1G. In other words, in a sampling-reconstruction system, CS1G is the sampling process, and SR is the reconstruction process, by taking the sample as the signal.
If you have this in mind, you then probably can have a better understanding of following references discussed in this section.

The problem discussed in [1] is that a signal can be reconstructed if certain requirements were met in both cases:

1. a signal is sparse in frequency domain, and under-sampled, in other words, missing samples, in time domain, 
2. or a signal is sparse in time domain, and under-sampled in frequency domain

They are actually CS1G problems, i.e., sampling a sparse signal in itself, and reconstructing the signal by solving the $\ell_1$ minimization.
For the first case, $x$ is the frequency components of the signal, $\tilde{\Phi}$ is inverse DFT basis, i.e. $IDFT(x) = \tilde{\Phi} x$  and $\Phi = R\tilde{\Phi}$ is the measurement matrix, where $R$ is a selection matrix, selecting $M$ rows of $\tilde{\Phi}$, $y$ is under-sampled time domain signal.
For the second case, $x$ is the time domain signal, $\Phi = R \tilde{\Phi}$ is the measurement matrix, where $\tilde{\Phi}$ is the DFT basis, $y$ is under-sampled frequency domain signal.
Thus, by taking the frequency domain components (first case), and time domain components (second case) as the original signal, respectively, the problem discussed is essentially a CS1G problem.

I'd like to also mention the following principle proposed in [1], which, I think, is the basic of following theoretical results.

1. Classical Uncertainty Principle: a function $f$ and its Fourier transform $\hat{f}$ cannot both be highly concentrated. $\Delta t \cdot \Delta w \geq 1$
2. [1] show a more general principle holds: it is not necessary to suppose that $f$ and $\hat{f}$are concentrated on intervals; instead, they can be just concentrated on a measurable set. $|T| |W| \geq 1-\delta$. And it also applies to sequences. $N_t \cdot N_w \geq N$
1. CT principle: missing segments of a bandlimited function can be restored stably in the presence of noise if (total measurement of the missing segments) $\cdot$ (total bandwidth) < 1.
2. DT principle: a wideband signal can be reconstructed from narrow-band data, provided the wideband signal to be recovered is sparse or "impulsive"

Then I have an intuitive understanding on he SMV/SR/CS1G theory: 

1. a signal cannot be both sparse in two incoherent basis
2. under-sample the signal in a non-sparse domain, and recover the signal in sparse domain

• then from the recovered sparse domain signal, we are able to get the original signal

And this is actually the CS2G theory, which do not require $x$ to be sparse in itself. We leave the discussion in next section.
[2]-[5] are a sub-group of researches, related to both CS1G and CS2G theory.
[2] actually discussed the SMV problem from SR's point of view. And it proposed more incoherent basis pairs besides (time, frequency). And these incoherent basis pairs are actually CS2G theory.
[3] improved the constrains related to the replacement of $\ell_0$ minimization with $\ell_1$ minimization in [2].
[4] proved that the condition in [3] is both sufficient and necessary, whereas [3] only proved the sufficiency.
[5] should be an extension of [2]. However, I didn't go into details.

[6] is about CS1G, and can be viewed as a direct extension of [1]. The problem discussed in the paper can be phrased as follows:

• a N-length discrete time signal $f$ is sparse in time domain, i.e., consists of a superposition of |T| spikes. 
• sub-sample the signal in frequency domain, i.e., only sample |$\Omega$|  frequency components, instead of N.
• If |T| $\leq C_M \cdot (\log{N})^{-1} \cdot |\Omega|$, then the reconstruction can be exact with probability at least 1-O($N^{-M^})
• the reconstruction is via solving $\ell_1$ minimization problem.

See, it is almost the same with [1] in this sense.

In addition, [6] shows that the min TV problem is actually the problem stated in the paper.

CS2G

As I stated before, 

1. a signal cannot be both sparse in two incoherent basis
2. under-sample the signal in a non-sparse domain, and recover the signal in sparse domain

The most classical CS theory is expressing this idea.
$y = \Phi x = \Phi \Psi \theta$.
To better understand the essence, we let ($\tilde{\Phi}, \Psi$) be a pair of incoherence basis, $\Phi = R \tilde{\Phi}^T$.
Then, in $\tilde{\Phi}$ domain, $x$ can be expressed as $\gamma = \tilde{\Phi}^T x$, in $\Psi$ domain, $x$ can be expressed as $\theta = \Psi^T x$.
So $y$ is actually achieved by under-sample the signal in non-sparse domain, i.e., $\tilde{\Phi}$ domain.
In other words, $y = R \gamma$. 
And the signal is reconstruct in sparse domain, i.e.,, $\Psi$ domain.
Then the CS1G is actually taking $\Psi$ as identity basis.

[7]-[9] are actually the theoretical foundation work on the CS2G theory, together with [2]-[5].
I didn't find the paper [7]. However, it is stated in [8] that [7] extended the result in [6], and showed the exact recovery holds for other synthesis/measurement pairs. And [8] describes these results, making reading [7] not so necessary. The results are shown as follows:

• an N-length signal $f$ is sparse in domain $\Phi$, i.e., $\theta = \Phi f$  has only a few nonzero entries.
• sub-sample the signal in domain $\Psi$, i.e., only sample $|\Omega|$ coefficients, instead of N
• the reconstruction can be exact, via solving an $\ell_1$ minimization problem.
• the requirement of the exact reconstruction is about the incoherence between $\Phi$ and $\Psi$.

[8] extended the work of [6] and [7], showing that the signal compressible, not necessarily strict sparse, in certain domain can also be optimally reconstructed, i.e., the reconstruction error using K measurements is as good as the best K-term approximation, with overwhelming probability.
[9] discussed the linear code corrupted by noise problem. However, the RIP condition is proposed in this paper, although it does not show the clear relationship between the decoding and CS. Besides, the Gaussian ensembles are proved to follow RIP with an overwhelming probability. On the other hand, it should be noticed that, if RIP is satisfied, the reconstruction is exact determinedly, whereas in [6] [7] [8], the reconstruction is with overwhelming probability.

Then [13] [14] organized all related theoretical results and formulate the CS problem.
And [12] gives a tutorial for CS theory, which I preferred to recommend for reading.

MMV

The only thing left is MMV. As is shown in the big picture, MMV is a direct extension of SMV, in a different way with the evolution from SMV to CS.
[11] formulate the MMV problem. Similar to SMV, the MMV can be viewed as either a 2D sparse representation problem, or a 2D CS1G problem.
[10], [15] give theoretical results on MMV, which is derived from those on SMV, i.e., [1]-[6].

Discussions

1. In this blog, I didn't discuss the development from noiseless to noisy case, which is also an interesting and important evolution.
2. In this blog, I didn't focus on the development from sparse signals to compressible signals.
3. In this blog, I only discussed the discrete-time situation. However, CS is actually can be, and should be addressed in analog signals, which is the meaning of "sensing".
4. Since I'm working on CS theory, my knowledge to SR, MMV is limited. Thus, the goal is to discern the CS with SR, SMV, MMV, instead of introducing SR, MMV, which I believe are far more complicated.
5. Return to the big picture, it is interesting to ask, can we extend MMV similar to the extension form SMV to CS? To the best of my knowledge, recent work of Duarte and Baranuik in [16] discussing the high-dimensional CS, where 2D CS is an special case. However, it differs with MMV in the reconstruction method, since it still solving the reconstruction problem in 1D. I would appreciate your help if you can share your opinions and references on this issue.
6. At last, I really hope this blog can smooth your perplexity when reading references where you don't know what SR, CS, SMV, MMV refer to. They are on the one hand synonyms and inherently similar, and on the other hand differ slightly from each other in terms of their representations and applications. By the help of this blog, you may have in mind what the reference is discussing when reading, at least, references given in the blog.

[1] Uncertainty principles and signal recovery
[2] Uncertainty principles and idea atomic decomposition
[3] A generalized uncertainty principle and sparse representation
[4] On sparse representation in pairs of bases
[5] Optimally sparse representation in general (nonorthogonal) dictionaries via l1 minimization
[6] Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
[7] The role of sparsity and incoherence for exactly reconstructing a signal from limited measurements
[8] Near-Optimal signal recovery from random projections: universal encoding strategies ?
[9] Decoding by linear programming
[10] Sparse representation for multiple measurement vectors (MMV) in an over-complete dictionary
[11] Sparse solutions to linear inverse problems with multiple measurement vectors
[12] An introduction to compressive sampling
[13] Compressive sampling
[14] Compressed sensing
[15] Theoretical results on sparse representations of multiple-measurement vectors
[16] Kronecker compressed sensing

Use IEEE Xplore to do a field study

Want to apply for a graduate program?
Want to know who are productive researchers in this area?
Here are some tips to help you do field study, by the help of IEEE Xplore.

1. Use advanced search
Input key words of this area, e.g. compressed sensing.
I suggest you use "OR" to add new filter words.
Click search.
2. See filters on the left side
Select "Publication Year" with certain range, e.g. 2007 - 2012
Click search again.

Then you will see a list of authors on the left side bar.
They are ordered by number of publications.
You would definitely know those productive researchers in your area.

Go to IEEE Xplore now and check it out~

Basic Understanding of Compressed Sensing

Purpose of this blog entry

During my research on CS, one problem is that I have read several papers related on CS, but different paper have different notations and explanations for CS. Besides, they also propose some new stuff in the paper. So  it takes me time to get to know the inner connections among these gorgeous references. As a result, I'd like to give a summary, according to my understanding, for the very basics of CS. Hope it will help you in your research.

What can CS do?

Well, intuitively speaking, CS is a way to sample and compress signals. You can use CS as a method to transmit or store a signal. One most immediate benefit of CS is that it samples and compresses signals at one time, thus reduces the complexity of encoder.

Why we need CS?

In following scenarios, we may turn to CS.

1) require simple encoder

2) require less bandwidth

3) sample high frequency component of signals, which cannot be sampled using traditional ways, e.g. MRI.

(Due to the limited knowledge of me, there are lots of scenarios omitted. If you have any suggestions, please be kindly inform me.)

Of course, if you want, you can use CS in whatever scenario that requires sample/store/transmit a signal. And the CS theory provides ways to reconstruct the sampled signals.

Signals

Please be advised that, some definitions used in this blog entry may differ from that in some papers. I use my definitions here because according to my understanding, it's better and easier for you to understand the connections between papers.

Let a signal $\mathbf{x} \in \mathbb{R}^N$ has its projection on an orthonormal basis $\mathbf{\Psi} \in \mathbb{R}^{N \times N}$ be $\mathbf{\theta} \in \mathbb{R}^N$, i.e., $\mathbf{\theta} = \mathbf{\Psi}^T \mathbf{x}$.

• $S$-sparse signal: $\mathbf{x}$ is called $S$-sparse in $\mathbf{\Psi}$ or has sparsity $S$ in $\mathbf{\Psi}$ if $\mathbf{\theta}$ has only $S$ nonzero entries.
• $C$-compressible signal: $\mathbf{x}$ is called $C$-compressible in $\mathbf{\Psi}$ or has compressibility $C$ in $\mathbf{\Psi}$ if $\mathbf{\theta}$ obeys a power law decay with an exponent of $-C-1/2$.
• power law decay: $\mathbf{\theta}$ obeys a power law decay if $|\theta|_{(i)} \leq R \cdot i^{-1/p}$, where $R > 0$ is a constant, $0 < p < \infty$, and $|\theta|_{(i)}$ is the $i$th largest magnitude entry, i.e., $|\theta|_{(1)} \geq  |\theta|_{(2)} \geq \cdots \geq |\theta|_{(N)}$.

Then $C = 1/p - 1/2$ for compressible signals.

Mostly, $C$-compressible signals consider only the case $0 < p < 1$, i.e., $C > 1/2$.
It should be noticed that $\mathbf{\theta}$ is also an $S$-sparse or $C$-compressible in $\mathbf{\Psi} = \mathbf{I}$, where $\mathbf{I}$ is an identity basis. Thus, to be precise, we need to consider/indicate in which basis the signal has what sparsity or compressibility. For example, a signal may have sparsity 10 in Fourier basis, but may have sparsity 20 in DCT basis. Some papers would not indicate the sparsity

Best $J$-term approximation
To approximate a signal $\mathbf{\theta}$, we can use the largest $J$ terms (in magnitude) in it, i.e., $\mathbf{\theta}_J$. Therefore,

1. if $\mathbf{\theta}$ is $S$-sparse in $\mathbf{I}$, then the best $J$-term approximation would have an approximation error equal to 0 if $J \geq S$, i.e., $\mathbf{\theta}_J = \mathbf{\theta}$.
2. if $\mathbf{\theta}$ is $C$-compressible in $\mathbf{I}$, then the best $S$-term approximation would have an approximation error equal $||\mathbf{\theta} - \mathbf{\theta}_J||_1 \leq G_C \cdot R \cdot J^{-C+1/2}$ and $||\mathbf{\theta} - \mathbf{\theta}_J||_2 \leq G_C \cdot R \cdot J^{-C}$, where $G_C$ is a constant only depend on $C$.

Meanwhile, we should indicate which basis does the best $J$-term approximation consider, e.g., $\mathbf{\theta}_J$ is the best $J$-term approximation in $\mathbf{I}$.

Then, we also say a best $J$-term approximation of $\mathbf{x}$ in $\mathbf{\Psi}$ is $\mathbf{x}_J$, i.e., $\mathbf{\theta}_J = \mathbf{\Psi}^T \mathbf{x}_J$ is the best $J$-term approximation of $\mathbf{\theta = \Psi}^T  \mathbf{x}$ in $\mathbf{I}$. Similarly, we need to consider two attributes when saying a best $J$-term approximation: 1)$J$ and 2)$\mathbf{\Psi}$.

Another thing should be noticed is that since $\mathbf{\Psi}$ is an orthonormal basis, $||\mathbf{x} - \mathbf{x}_J||_2 = ||\mathbf{\theta} - \mathbf{\theta}_J||_2 \leq G_C \cdot R \cdot J^{-C}$, i.e., the MSE has a power law decay. With $J$ increasing, the MSE would decrease.

How CS works?
Generally speaking, CS samples a signal $\mathbf{x}$ using $\mathbf{y = \Phi x = \Phi \Psi \theta = A \theta}$.

• $\mathbf{A} \in \mathbb{R}^{K \times N}$: sensing matrix, $\mathbf{A = \Phi \Psi}$.
• $\mathbf{\Phi} \in \mathbb{R}^{K \times N}$: measurement matrix

(I was ever confused the sensing matrix with measurement matrix...)

In this way, the signal is compressed in $\mathbf{y} \in \mathbb{R}^K$.

Reconstructing the signal from $\mathbf{y}$ can be achieved by solving a convex optimization problem, i.e., $\min ||\mathbf{\theta}||_1$ s.t. $\mathbf{y = \Phi \theta}$ by knowing $\mathbf{y}$ and $\mathbf{\Phi}$, and then using $\mathbf{x = \Psi\theta}$ to get $\mathbf{x}$ back. In other words, you can solve $\min ||\mathbf{x}||_1$ s.t. $\mathbf{y = A x}$ by knowing $\mathbf{y}$ and $\mathbf{A}$. They are equivalent.

The foundation of CS theory is to prove that in this sample-reconstruct process, the information in $\mathbf{x}$ can be preserved, and thus $\mathbf{x}$ can be well reconstructed.

In the following demonstration, I will not show you how the theory evolves, rather than how to prove the result. If you like, you can refer to papers I cite to see the details. And a tip for your reading is that please notice what the choice of $\mathbf{A, \Phi, \Psi}$ in CS.

At the very beginning, the idea of CS is presented in [1]. In that paper, it proved that for an $S$-sparse signal in Fourier basis, using CS, the reconstruction would be exact with an overwhelming probability at least $1 - O(N^{-\alpha})$ provided that $K \geq G_\alpha S \log{N}$, where $G_\alpha > 0$ is a constant only depend on the accuracy parameter $\alpha$. That is to say, for a given desired probability of success, a sufficient condition for exactly reconstruction is $K \geq G_\alpha S \log{N}$. It should be noticed that in some paper, it also gives a necessary condition with a similar result, please do not mix them up.

The choice of $\mathbf{\Psi}$ is Fourier basis. The choice of $\mathbf{A}$ is a random selecting matrix, i.e., randomly selecting $K$ elements from $\mathbf{\theta}$, e.g. $\mathbf{A}$ = [0 1 0 0 0; 0 0 1 0 0] which extracts the second and third elements of $\mathbf{\theta}$. Thus $\mathbf{\Phi} = \mathbf{A \Psi}^T$ can be generated accordingly.

It can be seen that if a signal is $S$-sparse in another basis $\mathbf{\Psi}$, CS can still reconstruct it using this way to generate $\mathbf{A}$ and $\mathbf{\Phi}$ by knowing $\mathbf{\Psi}$.

Furthermore, in [4],they extended these results and showed that exact reconstruction hold for other $(\mathbf{\Phi, \Psi})$ pairs.

Then in [2], it began to consider a $C$-compressible signal. It showed that using CS, the reconstruction is optimal with an overwhelming probability at least $1 - O(N^{-\rho / \alpha})$. By optimal, it means that it is generally impossible to obtain a higher accuracy from any set of $K$ measurements whatsover. The reconstruction error obeys $||\hat{\mathbf{x}} - \mathbf{x}||_2 = ||\hat{\mathbf{\theta}} - \mathbf{\theta}||_2 \leq G_{C, \alpha} \cdot R \cdot (K / \log{N})^{-C}$, where $\hat{\mathbf{x}}$ and $\hat{\mathbf{\theta}}$ is the reconstructed signals, $G_{C, \alpha}$ is a constant depending on $C$ and $\alpha$. This indeed says that if one make $K = O(J\log{N})$ measurements using CS, one still obtains a reconstruction error equally as good as using best $J$-term approximation. In other words, the following two cases have similar reconstruction error: 1) knowing everything about $\mathbf{\theta}$ and selecting $J$ largest entries of it, 2) reconstructing $\mathbf{\theta}$ using $K = O(J\log{N})$ measurements without any prior knowledge on it.

In [2], the choice of $\mathbf{\Psi}$ is can be any orthonormal basis and it provided three ways to generate $\mathbf{A}$: 1) Gaussian ensembles; 2) Binary ensembles; 3) Fourier ensembles.

Before goes go, I'd like to introduce the so-called restricted isometry property (RIP). For each integer $k = 1, 2, \dots$, define the $k$-restricted isometry constant $\delta_k$ of a matrix $\mathbf{A}$ as the smallest number such that $(1-\delta_k)||\mathbf{\theta}||_2^2 \leq ||\mathbf{A \theta}||_2^2 \leq (1 + \delta_k) ||\mathbf{\theta}||_2^2$ holds for all $S$-sparse signal vector $\mathbf{\theta}$ in $I$ with $S \leq k$. Therefore, $\mathbf{A}$ should have more than one restricted isometry constant since we can choose any $k$. Usually, we say a matrix $\mathbf{A}$ obeys RIP of order $S$ if $\delta_S$ is not too close to 1.

Then a stronger result is introduced in [5] and [6] (and stated in [3]), which says that, if the $k$-restricted isometry constant $\delta_k$ of $\mathbf{A}$ satisfies certain constraints (with different $k$), e.g. $\delta_{2S} \leq \sqrt{2} - 1$ (several other constraints are stated in [5] and [6]), then the reconstructed signal $\hat{\mathbf{\theta}}$ obeys $||\hat{\mathbf{\theta}} - \mathbf{\theta}||_2 \leq G_0 \cdot ||\mathbf{\theta} - \mathbf{\theta}_S||_1 / \sqrt{S}$ and $||\hat{\mathbf{\theta}} - \mathbf{\theta}||_1 \leq G_0 \cdot ||\mathbf{\theta} - \mathbf{\theta}_S||_1$ for some constant $G_0$, where $\mathbf{\theta}_S$ is the best $S$-term approximation of $\mathbf{\theta}$ in $\mathbf{I}$. This is deterministic, without any probability of success.

To go a step further, you will see that the result is in consistent with previous results. If you replace $||\mathbf{\theta} - \mathbf{\theta}_S||_1$ using the result in "Best $J$-term approximation", you will see the magic.

Then the question comes, how to generate a sensing matrix $\mathbf{A}$ satisfies the requirement of RIP?

How to generate sensing matrix $\mathbf{A}$?
There are lots of ways to generate a sensing matrix $\mathbf{A}$. I'd rather let you refer section "RANDOM SENSING" in [3] for a review. Here I just want to talk about two most common ways: 1) from $\mathbf{A}$ by sampling $N$ column vectors uniformly at random on the unit sphere of $\mathbb{R}^K$; 2) from $\mathbf{A}$ by sampling i.i.d. entries from the normal distribution with mean 0 and variance 1/K. With an overwhelming probability, these matrices obey the RIP constraints (e.g. $\delta_{2S} \leq \sqrt{2} - 1$) provided that $K \geq G \cdot S \log{(N/S)}$, where $G$ is some constant depending on each instance.

Another interesting property is that the RIP constraints can also hold for sensing matrix $\mathbf{A = \Phi \Psi}$ where $\mathbf{\Psi}$ is arbitrary orthonormal basis and $\mathbf{\Phi}$ is an $K \times N$ measurement matrix drawn randomly from a suitable distribution, e.g., with an overwhelming probability, provided that $K \geq G \cdot S \log{(N/S)}$, $\mathbf{A}$ obeys the RIP constraints. This makes CS sampling easier, because we only need to generate a measurement matrix $\mathbf{\Phi}$ without knowing $\mathbf{\Psi}$ at the encoder side.

A reading tree/graph for basic understanding of CS theory

If you read papers from the top layer to bottom layer, you should have deeper and deeper understanding about CS theory.

     

References

[1] Robust Uncertainty Principles: Exact Signal Reconstruction From Highly Incomplete Frequency Information

[2] Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?

[3] An Introduction To Compressive Sensing

[4] The Role of Sparsity and Incoherence for Exactly Reconstructing a Signal from Limited Measurement
[5] Stable signal recovery from incomplete and inaccurate measurements
[6] Compressed sensing and best k-term approximation

IEEE Transaction Starter: How to Start Writing a IEEE transaction paper

Here I want to show tasks that helps you get to know how to write a paper for IEEE transactions.

1. Visit "IEEE Author Digital Tool Box"
http://www.ieee.org/publications_standards/publications/authors/authors_journals.html
and Read "Instructions" for different Templates.
You may need only read the instruction for the template you will use. Here we focus on the "Instruction Only" in the "Template fors Transactions" part.
http://www.ieee.org/documents/TRANS-JOUR.pdf
* In this step, you will have a basic knowledge on the rules of writing a paper in IEEE society, especially for transactions and journal.
2.1 For MS Word users,
2.1.1 please download "Template and Instructions on How to Create Your Paper".
http://www.ieee.org/documents/TRANS-JOUR.doc
2.1.2 Please follows the instruction in the document to create your paper.
2.2 For Latex users,
2.2.1 You need to download "Transaction Style File", either "Unix LaTeX2e Transactions Style File", http://www.ieee.org/documents/IEEEtran.tar.gz
or "WIN OR MAC LaTeX2e Transactions Style File".
http://www.ieee.org/documents/IEEEtran.zip
* The Bibiliography file is included in the file (under the directory of "bibtex").
2.2.2 Read the "IEEEtran_HOWTO.pdf" to know how to use the style file.
2.2.3 Read the "IEEEtran_bst_HOWTO.pdf" under "bibtex" directory to know how to manage bibliography.

After finish these simple tasks, you should have a basic knowledge on the technical issues for your paper.

推荐一个GTD软件: doit.im

以前博主一直用mGSD（http://mgsd.tiddlyspot.com/#mGSD）来作GTD管理 mGSD是一个基于tiddlywiki的应用 基本GTD的功能都实现了 并且有着tiddlywiki的特点：单HTML文件
所以方便跨平台 也方便到处携带

对于有多台常用电脑的 我一般使用GitHub或者Windows Live Mesh进行同步管理

但是它有一个比较致命的弱点 也是tiddlywiki一直存在的问题 对于移动设备的支持 没有再ipad android phone上的app支持

所以博主最近发现一个免费的app： doit.im (http://doit.im/)
它可以在android和apple的移动设备上使用 也可以通过web使用
并且在GTD的功能方面 除了正常的功能外 还有
1. 收集箱功能 用于存储暂时无法归类的项目
2. 闹钟提醒功能 并可以设置多个提醒时间
3. 优先级功能
4. 过滤器
5. 与google calendar同步 这个功能对于博主这种google用户太有用了

但是还是有一些小缺点的 比如没有review机制等 但是根据官方的说法 9月份左右应该就会更新了

另外，对于windows桌面版，官方说法是还在开发，以前的版本仍能在http://support.doit.im/entries/21392588-doit-im-for-windows0-9-1 下载到，也能使用，据说有BUG。

再最后说一下，这个是国产的软件，而且个人觉得做的比较好的。听说最近也获得了投资，所以博主表示强烈支持。最近推出Pro收费，如果做得好的话，也会尝试使用的。

Windows 7无法休眠？

昨天突然发现windows 7没法休眠了
症状是：
点休眠后屏幕会黑一下 然后就进入到了Login的画面了-。-

在网上搜了半天：“windows 7无法休眠”之类的
基本上都在说什么：更新驱动哇，设置power configuration之类的。。
都没用。。。

正在郁闷 于是用英文搜了一下 windows 7 cannot hibernate
（休眠是Hibernate 睡眠是sleep 哈哈~）
终于眼睛一亮看到一个[Solved]GRUB + Windows 7 = Can't put windows to sleep/hibernate
特别是这个solved哇 真是救命稻草哇
链接如下：http://ubuntuforums.org/showthread.php?t=1341694

然后基本按照里面的步骤 就OK了

如果你的电脑也装了ubuntu之类的 应该就是这个问题没跑儿了
如果你只有windows... 那就另寻他法吧-。-

这里我把英文大概翻译一下~

症状：
在装了Windows 7之后装Ubuntu双系统的机子（这个双系统的顺序也是有讲究了。。主要是看你是不是用GRUB引导系统），这个你就把GRUB装在了MBR上，这个就会导致Windows没法进入sleep or hibernate模式（这个屏幕会黑一下，然后直接回来）。用WIN7的DVD恢复这个MBR到原来的状态呢是可以解决的，但是会让你的GRUB又没法工作了...

实际问题：
要让sleep/hibernate工作，第一个windows的分区必须是标记为boot，即使里面装了GRUB。

解决方案：
在Ubuntu下， 使用gparted(如果没装的话 sudo apt-get install gparted。使用就是sudo gparted)。在你的boot driver（通常是/dev/sda)，确保第一个windows分区是标为boot的。然后重启就OK了

P.S. 这个帖子的回复也值得一看~

一般用Thinkpad的同学常常会遇到这个问题，因为Thinkpad有个默认的分区SYSTEM_DRV在C盘之前。一般它是作为boot分区的。所以我们只要把Windows系统分区作为boot就好了。

这个故事告诉我们，掌握英文搜索能力很重要...

jQuery中设置click事件的参数

(部分转自百度知道)


【问题】
原来html中onclick出发js方法可以传递参数
<a href="#" onClick="showFile('view');">aaaaa</a>
<script>function showFile(fun){}</script>
但是 现在用jquery的click事件怎么传递这个参数？
<a href="#" id="fun">aaaaa</a>$("#fun").click(function () { });


【解答】
1. jQuery的click事件不能直接传递参数，
如果使用 $('#fun').click(choose("val"));
会导致在运行这个语句时直接运行choose函数。


应该使用 $('#fun').click(choose);
function choose() {
//...
}


2. 可以把
$('#fun').click(function () {
});
看作一个function声明,
就相当于onclick的事件声明;

$('#fun').click(function () {
function()(调用的方法)
});


3. 可以使用标签内的attr来获得关于此标签的参数
<a id="fun" testvalue='abc' href="#" onClick="showFile('view');">aaaaa</a>
$('#fun').click(function () {
alert($(this).attr('testvalue'));
alert($(this).text());
alert($(this).attr('href'));
//......
});

jQuery获取input标签的值

一般来说，用js获取input标签内的值会用
<input id="p_folder"></input>
var p = document.getElementById("p_folder");
var pV = p.value;


但是jQuery中，如果写成
var p = $('p_folder');
var pV = p.value；
将无法获取到标签内的值,


这是因为
$("")是一个jQuery对象，而不是一个DOM element
value是DOM element的属性，对应jQuery的val
val():获得第一个匹配元素的当前值
val("val"):设置每一个匹配元素的值为val


所以上面的code应该写成
var p = $('p_folder');
var pV = p.val();

Summary of Compressed Video Sensing

[1] proposed to use cs on stream video by sample several frame together or independently.... But it didn't consider the interframe redundancy.

[2] was focus on increasing the resolution of digital video, thus little work was done for video coding/compression.

[3] [4] proposed compressed video sensing in  2008.
[3] used a hybrid way to compress video. The main contribution I think was only the scheme it proposed: transmit both conventionally encoding(low resolution) and cs encoding(high resolution) video stream, recon. on demand (if coarse-scale -> conventionally decoding, if fine-scale, cs decoding).
Compared to [3], I think [4] is much important for CVS. The way it employed is classifying the blocks of a frame to dense and sparse via a cs testing. Dense blocks use conventional encoding, while sparse blocks use cs. The cs testing for a block of frame is another contribution should be noticed.

In 2009, most work were focus on distributed CVS based on the notion of Distributed Video Coding(DVC). [5] use reconstructed key frame to find sparse basis for cs frame, and it proposed L1, SKIP, SINGLE modes for cs frames. The codec is quite similar with pixel-domain dvc. [6] also use reconstructed key frame to generate side information. But its side information is not the sparse basis, but a prediction. Furthermore, [6] use both frame-based and block-based encoding for cs frames. It is quite novel. But I think although it improves the performance, but a little redundant. Different with [5][6], [7] use cs for both key frame and non-key frame. And it proposed the modified GPSR for DCVS. Furthermore, there are relatively complete review of techniques like cs, dvc, dcs, etc., which I think is quite useful for beginners in this area.

[8] proposed a very interesting multiscale framework. It employs LIMAT[11] framework to exploit motion information and remove temporal redundancies. And it use iterative multiscale framework: reconstructing successively finer resolution approximation to each frame using motion vectors estimated at coarser scales, and alternatively using these approximation to estimate the motion. The multiscale framework essentially exploit the feature of wavelet transformation (coarse scale and fine scale).

[10] is published in 2011. It designs the cross-layer system for video transmission using compressed sensing.
The cross-layer system jointly controls video encoding rate, transmission rate, channel coding rate. It is useful for researchers who focus on network design of a compressive sensing application.

[9] is not about CVS, but I think it's very important to know current video compression techniques. It introduced the video compression techniques like H.26x, MPEG, etc. It's a very good introduction and review work.

Another thing should be mentioned is that, Distributed Compressed Video Coding in [5] [6] both used the notion: the sparsest representation of a frame is a combination of neighbor blocks of a block.

[1] Compressive imaging for video representation and coding
[2] Compressive coded aperture video reconstruction
[3] Compressed video sensing
[4] Compressive Video Sampling
[5] Distributed video coding using compressive sampling
[6] Distributed compressed video sensing
[7] Distributed compressive video sensing
[8] A multiscale framework for compressive sensing of video
[9] Video Compression Techniques: An Overview
[10] Compressed-Sensing-Enabled Video Streaming for Wireless Multimedia Sensor Networks
[11] Lifting-based invertible motion adaptive transform framework for highly scalable video compression

Review of the size of Measurement Matrix in Compressed Sensing

* This article is only a review for my personal use. There may have some mistakes. Please do not trust in this article.
* If you noticed any mistakes in this article, please notify me. Thanks a lot.

In the following description, M is the number of measurements needed, N is the length of signal, K is sparsity, Φ is measurement matrix, Ψ is sparse basis. C is a constant.
$Y = AX = \Phi\Psi X$

The requirement for $M$
[1] Sparsity and Incoherence in compressive sampling
$M \geq C \cdot \mu^2(\Phi, \Psi) \cdot K {\text log}N$

[2] An introduction to Compressive Sampling
Form A obeying RIP i)-iv)
$M = O(K {\text log}(N/K))$
$M \geq C \cdot K {\text log}(N/K)$
i)-iii) see
[3] A simple proof of the restricted isometry property for random matrices
iv) see
[4] Uniform uncertainty principles for Bernoulli and sub-gaussian ensembles

Form A by first finding paris of incoherent orthobases $\Phi, \Psi$, and then exracting $M$ coordinates uniformly at random using R: $A = R\Phi\Psi$.
$M \geq C \cdot ({\text log}N)^4$
$M \geq C \cdot ({\text log}N)^5$ for a lower probability of failure
see [6] and [7] On sparse reconstruction from Fourier and Gaussian measurements

[6] Near-optimal signal recovery from random projections and universal encoding strategies
[8] Compressed Sensing, D.L.Donoho
[9] Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
[10] Neighborliness of randomly projected simplices in high dimensions
[11] High-dimensional centrally symmetreic polytopes with neighborliness proportional to dimension
$M = O(K {\text log}(N))$
$M \geq C \cdot K \cdot {\text log}N$

[12] Compressive Sensing, R.G.Baranuik
$M \geq C \cdot K {\text log}(N/K)$
it cited the result from [8] and [9]. Are they the same?

To summary, there are 4 expressions:
1)
$M = O(K {\text log}(N))$
$M \geq C \cdot K \cdot {\text log}N$
2)
$M \geq C \cdot K {\text log}(N/K)$ 
3)
$M \geq C \cdot ({\text log}N)^4$
$M \geq C \cdot ({\text log}N)^5$
4)
$M \geq C \cdot \mu^2(\Phi, \Psi) \cdot K {\text log}N$

1) and 2) are quite similar with each other; 1) is noisy situation and 2) is noiseless.
4) is quite similar with 1), except the parameter $\mu^2(\Phi, \Psi)$, which is a measure for the incoherence between the two matrix.

Some Ideas

记录下最近的idea
最主要的project还是paper wiki 希望能在放假前搭好这个平台

又想做一个类似吾志 但是只是记录/share dream的网站 创意来源于xxxHolic的梦买 这个可能需要更多的考虑 比如是否应该做成一个网站还是只是一个现有SNS的app 如果是APP 怕破坏的这个idea的pure goal 但是做成一个website 又觉得没有特别大的市场 需要数据库支持etc..
但是似乎做起来不难 只是要去找现成的框架

还想做一个创意分享网站 关注于生活中想到的小创意 寻找有类似创意的人一起开发app之类的 或者像服务商提供需求建议 etc.
还是觉得这种类型的网站 美工很重要的样子

还想做一个类似WikiCFP的网站 主要用于发布/收集各类竞赛信息 方便高校学生查询/参与 帮助企业推广竞赛 这也是因为发现很多competition都在想方设法提高自己的知名度 这个似乎做起来也不难 几乎可以完全copy WikiCFP 不过后期做好也需要美工方面的UI设计

还有一些实现有些困难的东西了 呵呵
比如，做一个做饭/洗碗机器人 可以输入菜谱程序 然后就可以做饭了~。~ 还可以定时做饭 远程控制做饭...
* 这个还可以开发app平台 做一个app推荐菜谱 or 根据家里的菜规划要做的菜（对于一次买N天菜的人） 提醒菜过期...
还有就是智能白板（笔） 可以在玻璃板/白板上演算/演示/记录... 然后用笔选取区域 即可传送到终端（电脑 打印机....）

可是都不是我的专业 也不能用来作为现在的Research 只能业余的时间做做了
要是不用学习不用工作就可以生活 估计就可以专心做这个了
大概只能继续读PhD了吧 呵呵

Enable Latex / Math Formula in Blogger

MathJax can help you with this.
See http://irrep.blogspot.com/2011/07/mathjax-in-blogger-ii.html for the instruction.

It's awesome.

Summary of Block Compressed Sensing on Image

Last article, I briefly introduce existing cs method on image. This article aims to summary how block cs worked on image.

Before I go on, I need to introduce something about measurement matrix.

Currently, there are several way to generate a measurement matrix. For a complete list of possible measurement matrix, please refer to  https://sites.google.com/site/igorcarron2/cs . Here I only discuss three of them: 

• Random Fourier Ensemble: The signal is a discrete function f on Z/NZ, and the measurements are the Fourier coefficients at a randomly selected set Omega of frequencies of size M ( A is an M x N matrix.)
• Gaussian ensemble: A is an M x N matrix (M x N Gaussian variables).
• Bernoulli ensemble: A is an M x N matrix (M x N Bernoulli variables). 

It should be noticed that for most of the case, the measurement matrix should be orthonormal.

For 1d signal, Gaussian ensemble is enough to reconstruct the signal[1]. However, for 2d image,  N can be fairly large, which makes the storage and computations of a Gaussian ensemble very difficult. Thus, [2] suggested to apply a partial random Fourier matrix。For sparse basis, it employed wavelet. Besides, it uses min tv instead of l1norm as recon strategy. However, I've found no simulation code available for [2].

Another possible way to solve the problem addressed before is to sample the image block by block. This is quite similar with what JPEG did. [3] gives out corresponding research. For measurement matrix, the paper uses i.i.d Gaussian ensembles. For sparse basis, it uses LT. The reconstruction is based on PoCS and Hard Thresholding . No simulation code available now. But you may refer to https://sites.google.com/site/igorcarron2/cscodes. There is a code called sbhe.m, 

Implemented from Fast compressive imaging using scrambled block Hadamard ensemble by Lu Gan, Thong Do and Trac Tran. This is another algorithm proposed by the same author. It may help you.

To improve the performance of [3], [4] proposed to first decompose the coefficients into dense and sparse component. For dense component, it uses conventional encoding; for sparse component, it uses cs. For measurement matrix, it didn't clearly indicate in the paper. But from inference, it should use i.i.d Gaussian ensembles as in [3]. It still employs wavelet as sparse basis. The reconstruction is based on PoCS[2] and prediction by adaptive interpolation. The paper gives out the detailed reconstruction scheme. No simulation code available now.


After that, [5] gives some interesting simulation results. Here for measurement matrix, it should still use i.i.d Gaussian ensembles.But for sparse basis, it proposed to use Directional Transformation(CT and DDWT).The reconstruction is based on SPL. Simulation code is available at http://www.ece.msstate.edu/~fowler/BCSSPL/. Besides I am quite interested in analyzing the EXPERIMENTAL RESULTS part in this paper. It compares with several other methods.
1. To compare the effectiveness of CT and DDWT, it compares to BCS-SPL-DWT, BCS-SPL-DCT. The simulation code is not available now.
2. To compare SPL with TV, it compares with BCS-TV. The implementation is using l1-Magic(http://acm.caltech.edu/l1magic/). I have implemented the code at http://www.ualberta.ca/~hfang2/pub/Block CS-TV.zip .
3. To compare SPL with GPSR and SAMP, it uses the implementation provided by their respective authors(http://www.lx.it.pt/~mtf/GPSR/ http://thongdojhu.googlepages.com/samp_intro/ ).

The last one is [6]. It perform random permutation among blocks to achieve better performance. It uses DCT as sparse basis. For measurement matrix, it uses i.i.d Gaussian ensembles.It uses min l1-norm instead of min tv as reconstruction method. I recommend you use cvx_toolbox(http://cvxr.com/cvx/download/) for simulation.

If you find any simulation code published, or any error in the article, please contact me.
Thanks a lot.


[1] Robust uncertainty principles: Exact signal reconstruction form highly incomplete frequency information
[2] Practical Signal Recovery from Random Projections
[3] Block Compressed Sensing of Natural Images
[4] Image Representation by Compressed Sensing
[5] Block compressed sensing of images using directional transforms
[6] Compressive Sampling With Coefficients Random Permutations for Image Compression

Compressed Sensing(压缩感知)用于图像的综述

CS最初由[1][2][3]提出。[1, 2]没有看，[3]中理论推导比较多。我建议读[4]作为入门。
最初的CS理论只提出了noiseless的情况下，可以accurately recover compressible signal，注意是需要compressible signal的，不过大多数信号的是compressible signal,所以适用面很广。
于是有人就会想在noisy的情况下，是否可以使用CS呢？
最初的研究是，Noisy measurements的恢复效果不是很好。所以Wisconsin的俩人J. Haupt和R. Nowak就对zero-mean additive noise的情况进行了研究，相关工作可以参看[5]。他们的结论当时是可以在这种加性噪声的情况下恢复原信号（否则就没法发paper了...）。
对之后CS方面的文献就不在这片文章里描述了。


接下来我想重点讲一下cs用于imaging的文献发展历程。
一般来说，研究都放在如何采样一个图像或者如何压缩一个图像。
对于2D的图像，由于维数较大，导致CS面临有以下几个问题：
1. 重建算法计算量大
2. 需要大量的存储空间来保存随机采样operator，即measurement matrix

05年的时候，在[6]中最初对2D图像信号进行了CS reconstruction并给出了其仿真结果，不过这篇文章只讨论了无噪的情况，而且没有给出有噪情况的分析。作者的主要方案是apply a partial random Fourier matrix in the wavelet domain。
06年[3]提出multiscale CS：different scales of wavelet coefficients are segregated and sampled with partial Fourier ensembles。
也是06年的时候，[9]就对CS是否能作为一种imaging method进行了检验，主要考虑有噪情况下是否能够有很好的性能，将其performance与标准的pixel-based采样方案进行比较。最终结论是：CS在以下情况下优于传统像素采样：

• if the underlying image is highly compressible or
• or if the SNR is sufficiently large

另外[9]还比较全面的介绍了对piecewise constant这个类别的图像进行压缩传统的做法。并给出了相应的squared approximation error作为性能衡量标准。

07年L. Gan基于[6]的理论提出了block compressed sensing[7]。这篇文章是我认为很多后续对图像压缩的研究的基础，非常建议一读。


08年MSRA的一帮人提出了将图像的coefficients进行分解[8]，对于dense的部分进行conventional encoding （变换编码），sparse的部分进行CS。


[7]和[8]都给出了PSNR效果，是很好的比照对象。


[14]是基于[6]的一个改进。除了算法部分，我推荐看一下Background这一部分，它比较完整的介绍了当前CS的一些算法。同时，这篇文章也对[6]进行了review，有助于理解[6]的算法。另外，这篇文章给出了不同CS算法下的PSNR，有比较系统的仿真结果，可供参考。


11年，[15]提出了基于[6]的另一种改进。作者对稀疏系数矩阵进行random permutation从而使稀疏度分布趋近一致，从而提高CS的性能。


08年T. Wan等人提出将cs应用于image fusion[10]，09年A. Divekar也作了类似的研究[11]。image fusion就是将从不同sensor对同一个场景的图像结合起来一发现其中的信息。有兴趣的同学可以看看这两篇文章，这里不多做解释。


09年开始，研究者开始考虑colored image，从而将CS从2D image转到了3D。[12]的作者提出使用Bayer Filter以及Joint Sparsity Model来exploit不同色彩信道之间的相关性。结果显示这种方法比普通的对各个信道独立进行CS效果更好。


08年，CS界的一位牛人J. Romberg使用noiselet概念（类似wavelet），并且使用min TV而不是min l1进行图像重建[13]。TV中的梯度运算可以促进smoothing，更加适合images。这也是大多数CS imaging的恢复算法。但是Noiselet用于稀疏基在图像方面的后续研究我还没有看到，有可能是我遗漏了。


以上就是05年到11年大部分关于cs用于image方面的paper综述，希望有助于大家理解。
有错误之处欢迎指出。


[1] Roubust uncertainty principles: Exact Signal Reconstruction from Highly Incomplete Frequency Information
[2] Near optimal signal recovery from random projections: Universal Encoding Strategies?
[3] Compressed Sensing
[4] Introduction to compressed sampling
[5] Signal reconstruction from noisy random projections
[6] Practical Signal Recovery from Random Projections
[7] Block compressed sensing of natural images
[8] Image representation by compressed sensing
[9] Compressive Sampling VS. Conventional Imaging
[10]Compressive image fusion
[11]Image fusion by compressive sensing
[12]Compressive imaging of color images
[13]Imaging via Compressive Sampling
[14]Block compressed sensing of images using directional transforms
[15]Compressive Sampling with Coefficients Random Permutations for Image Compression

Apache2.2 + PHP5.3.3 Windows下的配置

昨天给自己配了一下PHP的环境，弄了有一会。

网上的教程也看了，还是自己写一下，以后可以参考，呵呵。

首先要注意的是这个教程有几个前提要求：

1. Windows； Linux下的我没配过，所以不是很清楚。

2. Apache2.2；版本比较重要，不同的版本也有可能是不一样的配法~所以，如果是要配置其他版本的话，请换关键字搜索~~呵呵~

3.PHP5.3.3； 同样是版本的问题~

好了，现在开始配置吧。

1. 首先，先要下Apache2.2。我下的是httpd-2.2.16-win32-x86-no_ssl.msi，安装到C:\Program Files里了

2. 然后，把PHP5.3.3也下下来，注意，要下php-5.3.3-Win32-VC6-x86.zip这个文件，不要有nts，也不要是VC9什么的。我一开始就下错了，然后缺文件之类的- -。

这个就直接解压缩就好了，放在C:\php目录下。（这个目录底下应该就直接是文件了，不是解压得到的文件夹哦）。

3. 装好Apache之后，可以打开Apache服务，然后访问localhost一下，看看是不是装好了。基本上这步不会出问题的。

4. 配置PHP。

关键步骤~（我引用了http://www.blogjava.net/zyw090111/archive/2010/08/07/328197.html里面的方法），不过有一些注释的地方是我做错的点。

1） 配置PHP5.3.3，打开php安装目录（C:\php）可以看到目录下有两个这样的文件 php.ini-development和php.ini-production，第一个是开发使用的配置文件，第二个是标准的生产环境的配置。
2）选择php.ini-development复制一份到同目录下，并改名为php.ini使用文本工具打开，查找extension_dir，可以看到两个，选择On windows:

下面的那个并去得前面的分号修改为extension_dir = "C:/php/ext"，读者根据自己的目录结构配置，目的是找到和php.ini同目录下的ext文件夹中的扩展库。

！！这里一定要注意的是，不要只改了目录，而没有把分号去掉- -分号没去掉这句话是不起作用的。

检测方法是，写一个index.php文件

<? phpinfo()?>放在Apache的访问的文件夹下（可以查看Apache22/conf/httpd.conf,搜索DocumentRoot），默认是Apache22/htdoc这个文件夹。然后访问localhost/index.php，可以看到

Configuration File (php.ini) Path	C:/Windows
Loaded Configuration File	C:/php/php.ini

以及

extension_dir

C:/php/ext

C:/php/ext

这就说明配置对了，否则，需要在下面的步骤中把文件拷贝到相应目录。
3)查找extension=php_，去掉extension=php_curl.dll、extension=php_gd2.dll、extension=php_mbstring.dll、
extension=php_mysql.dll、extension=php_mysqli.dll、extension=php_pdo_mysql.dll、extension=php_xmlrpc.dll前面的分号。查找short_open_tag = Off把它修改成short_open_tag = On，让其支持短标签。

这一步的作用是开启一些功能，如curl，mysql等。而这些dll文件都是放在C:/PHP/EXT目录下的，也就是由上一步设置的extension_dir决定的。
4)复制php5ts.dll文件到WINDOWS/system32目录下，只有php-5.3.3-Win32-VC6-x86版本中才有php5ts.dll php-5.3.3-nts-Win32-VC6-x86版本是没有的。

5)复制libeay32.dll ssleay32.dll（C:/PHP）到C:/windows下。

（之所以有这一步，可能是因为类似的某个目录没有配好，默认在C：/windows下。但暂时我还不知道在哪配，所以也就只好默认了- -）

这样，php的配置基本就完成了、

免费软件打造你的学术PC

上一篇博文写的关于如何打造你的iPad成为学术利器
很多软件是和电脑之间需要同步的 所以 同步是下列软件共有的特点
另外 本篇博文还将介绍一系列自身管理的软件


1. Tiddlywiki + Git + Github
Tiddlywiki 是一款基于Html的单文件个人知识管理系统 十分容易上手
你可以在上面写whatever you want 随意记录你遇到过的各种问题以及如何解决
可以记录你的research diary
可以写paper review
etc...
而且它有很强大的plugin支持 可以安装各种你想要的功能
这么多个人知识管理系统里推荐他的原因是他是单文件 所以便携 任何场合只要有浏览器就能打开
另外他是唯一一个可以跨平台的wiki 你可以随意在windows linux mac之间切换
并且他和Git搭配起来功能可以发挥到极致

Git是一款版本管理软件 有过项目开发经验的同学都应该接触过这个软件
如果没有用过 强烈建议学习一下 很容易上手 对于代码的管理绝对是必不可少的软件
这里使用Git一是为了管理你的wiki版本 这样即使某个版本的wiki崩溃 也能很快回滚到之前的状态
另一个目的是同步 结合Github 你可以随时随地从你的github库上clone你的wiki 并且push你的修改 当然 你也可以使用dropbox等来完成类似功能（但是只有git才有这么强大的版本管理能力）

下面是我自己的两个基于tiddlywiki的实现，大家可以参考
我的tiddlywiki: http://funny.tiddlyspot.com
我的Homepage: http://hfang2.tiddlyspot.com

2. mGSD
对时间管理有一定了解的人都应该知道著名的Get Things Done
没有看过的同学强烈推荐看以下这本讲时间管理的书
现在有很多GTD的软件 这里介绍基于tiddlywiki的mGSD
个人对tiddlywiki情有独钟 当然喜欢它的各种应用
mGSD算是tiddlywiki中发展很健全的一个例子 它完全实现了GTD的所有功能
又有tiddlywiki的特性 当然你也可以搭配上git进行版本管理

3. Live Mesh
上次介绍过这个软件 这个软件的牛逼之处是你不但可以在不同电脑之间同步文件夹 还可以远程登录 简直就是神器啊！你可以在实验室让打开你的代码跑仿真 也可以在家里打开实验室电脑打印文件 总之 如果你有两个以上的常用电脑 这个软件绝对是TOP 1

4. MindManager
这是个思维导图软件 上次在ipad app推荐的时候推荐个这个软件
这也是为什么我推荐他的原因 他可以更好的和ipad搭配使用 他可以把文件上传到其网上空间 和ipad同步
当然 你也可以用freeMind/XMind 然后使用Dropbox和ipad同步 但是似乎ipad MindManager上兼容性还不是太好
不过 这个不是个免费的软件 但是我相信这难不倒我们强大人中国人民的智慧的~呵呵

5. Mendeley
好了 这个是个免费文献管理软件 这个软件可以把你的文献上传到网络空间 可以在不同电脑之间同步管理 同时可以在ipad上同步文献 随时随地看paper 呵呵

6. Dropbox
这也是 为了结合ipad使用的软件 可以随时同步你的文件 唯一的缺点就是必须把文件放在dropbox这个文件夹下 所以我之前介绍的Live Mesh就是为了弥补这个不足所用的软件

7. Evernote
强大的云笔记软件 可以随时在手机 平板 各处电脑记录事件 这可以弥补在手机上浏览mGSD不方便的问题 也可以作为记录一些备忘录的工具

8. Vim
超强的text editor 用过linux的人都应该知道它 比记事本强大很多
可以有很多配置 一开始用可能会不习惯 但是一旦上手 绝对是text editor中的神器

9. TexMaker
Latex编辑器 写paper的专业工具 在格式排版方面 比word好用很多

免费app打造你的学术iPad

iPad除了用来玩 对于researcher来说 当然也可以用来作为一个学术利器
下面介绍的应用基本上都是free的 所以无论你的ipad有木有越狱 都是ok的

1. Mendeley
   这是一款免费的文献管理软件 你可以在电脑上管理你的所有文献 同步到服务器端 在ipad上你也可以看到你电脑上所有的文献
2. Dropbox
   很强的一款同步文件的软件 可以在电脑和ipad之间同步很多文档 注册就有2G免费空间 它之所以强大是因为基本上需要用到数据共享的app（不管ipad android）都会整合dropbox 所以绝对是不可或缺
3. SlideShark
   播放PPT的软件 可以让你的ipad播放PPT文件 需要电脑通过软件Upload到服务器进行同步
4. 金山词霸
   没啥好说的 查单词
5. Caculator++
   免费的计算器软件
6. Evernote
   很好用的云端记事本软件 可以和电脑 手机同步 我用它来记一些小事情 其他事情我使用mGSD 一款基于tiddlywiki的GTD工具 有机会下次介绍
7. pdf-notes
   免费的看pdf的软件 并且可以作注释 功能很强大
8. CloudOn
   编辑 查看office文档的软件
9. iNoteBook Lite
   集合日历 日记 笔记 文档管理于一身的软件 有兴趣的朋友可以使用一下
10. PocketCloud
    远程登录电脑软件 可以在任何地方登录你的电脑
11. WifiSendFree
    让你的ipad成为电脑的键盘和鼠标
12. Mindjet
    思维导图工具 可以和电脑的MindManager一起使用 一个用来编辑 ipad主要用来演示 MindManager的破解版大家好好利用google就好了
13. Timeli
    项目日程管理软件 用户界面友好
14. OfficeDrop
    可以随时将纸质文档通过摄像头扫描保存为电子文档并上传到服务器保存
15. i-Clickr
    一款控制电脑PPT播放的软件 这个软件是收费的 但是是坐presentation的绝对利器 可以设置timer提醒时间 可以看ppt的备注 控制PPT播放 进行涂鸦等等 所以花钱买or越狱装都是值得的

推荐两款文件夹同步软件Live Mesh和SyncToy

大家现在不免有多台电脑 比如实验室一台 家里一台
所以同步文件夹就比较麻烦 需要用U盘拷来拷去

Dropbox是一款不错的同步软件 可以和tablet ipad等同步 但是他需要把所有的文件放在一个文件夹下 比较麻烦
Windows Live Mesh 是Microsoft推出的功能 可以将文件夹同步到网络端 从而在不同的机器上同步 而且注册就有5G的免费空间 并且可以远程登录桌面 非常好用

另一款软件SyncToy主要用于局域网同步或者本机文件夹备份 比较适合需要同步移动硬盘文件 或者同一个局域网的电脑文件夹 但是对于不同局域网的文件夹就比较复杂了

WikiCFP : Call For Papers of Conferences , Workshops and Jounals

发现一个网站 可以用来关注最近开的conferences workshops等消息

也可用来发布消息

WikiCFP : Call For Papers of Conferences , Workshops and Jounals

X10i Root 2.3.3教程

系统要求：
android 2.3.3

准备工作：
下载 Flashtool0.4.2.0.rar

Root

1. 安装驱动
   1. 解压缩 flashtool/drivers 中的X10_ADB_drivers.zip
   2. 设备管理器-> X10 （未知USB设备）-> 更新驱动 （选择文件夹 Flashtool -> drivers)
2. 打开X10FlashTool.exe
3. 手机设置 未知来源 （设置->应用程序）和 USB调试，保持唤醒（设置->应用程序->开发）
4. 连接手机
5. 等待Root图标亮起 点击ROOT
6. 期间会重启
7. 显示'root access allowed'，表示root成功

图文教程可以参考：http://sebbs.cnmo.com/thread-10614705-1-1.html

FAQ:

• Root图标不亮起是为什么？

检查驱动是否安装成功（按照步骤1）

• 刷机失败 启动时一直卡在开机画面

如果驱动没有安装正确，或者没有开启未知来源和USB调试，或者使用低版本的FlashTool，都有可能出现该情况
可以用update service（SE提供的更新软件 升级过系统的人应该都知道）重新更新一遍就好了

TrackMyTour: 记录旅行的iPad app

可以在当前地点创建图片 纪录 有点像日记 不过结合地点和图像 很有意思

Clibe: 一个有意思的记笔记的iPad app

之前一直用的是Evernote 当然很好用
不过clibe不同的是 它可以作手写板 可以涂鸦 可以随意乱画
而且能够创建不同的笔记本
可以用来头脑风暴 做小型思维导图

推荐大家试用 免费的咯

The reason for using 8x8 as the block size in image processing

The DCT usually use 8x8 as the block size to be applied to images. This is a trade-off between computational complexity, compression speed and quality.

A lot of research work show that after 15 or 20 pixels, the relationship among them begins to reduce; that is to say, a group of similar pixels usually lasts for 15 to 20, after that, the amplitude would change.