# Compressed sensing, approximately sparse, Power law

An x in $\mathbb{R}^n$ is said to be sparse if many of it's coefficients are zeroes. x is said to be compressible(approximately sparse) if many of its coefficients are close to zero.ie Let $x=(x_1,x_2,....x_n)$. Sort the absolute values of the coefficients in decreasing order with new indices as $|x_{(1)}|\geq|x_{(2)}|\geq,..,|x_{(n)}|$. x is said to be compressible if $|x_{(k)}|\leq C k^{-r},r>0$ for all $k=1,2,..,n$ where $C$ is a fixed constant. Coefficients $x_k$ don't follow any probability distribution.

My questions:

1) With this definition, every $x\in\mathbb{R}^n$ satisfies this power law as I can always find a constant(because I have only finite values) $C$ such that above power law is satisfied. But this shouldn't be the case because not every $x$ in $\mathbb{R}^n$ is compressible.

2)How do I choose $C$ so that this definition makes sense?

3) Is this definition even right? What am I missing?

• Are you sure the term compressible wasn't defined for infinite sequences? – dls Mar 19 '12 at 20:40
• You probably should know more about the $x$'s to make it right. Are they a result of some measurement/calculation? – yohBS Mar 19 '12 at 20:47
• @ dls- yes, It is defined for finite dimensional signal. It may be defined for infinite dimensional but in my case it is for finite set of values. – Maan Mar 19 '12 at 22:52
• @yohBS: So you are saying that this definition is wrong as it is written. x is just an n dimensional vector. It can represent the coefficient of some vector when written in some basis. – Maan Mar 19 '12 at 22:56
• Then maybe the definition is related to the thing that creates the signal. For a specific, given $n$-dimensional vector it is clearly meaningless. But maybe it makes sense for a family of signals. For example - sampling the electric field at given distances from a point charge, where the position, magnitude of the charge and direction of sampling varies, but you know that after sampling enough points it will decay as a power law. I'm just guessing here. – yohBS Mar 19 '12 at 23:02

Definition is correct. $C$ is defined for any vector $x$, so you can't first choose $x$ and after that C. You can say that $x$ is $C,r$-compressible (or not) for fixed $C$ and $r$.
The definition looks just like the rule for determining convergent series. Using the ratio test, you can tell if a sequence of roots converges. As I recall, $\frac{1}{x}$ doesn't converge to zero. Rational values of $r$ don't converge quickly, $\frac{1}{\sqrt{x}}$, I wouldn't bet any money that's a sparse system. Are you sure $r > 0$ and not $r > 1$ ?