1
$\begingroup$

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?

  • 1
    Are you sure the term compressible wasn't defined for infinite sequences?2012-03-19
  • 0
    You probably should know more about the $x$'s to make it right. Are they a result of some measurement/calculation?2012-03-19
  • 0
    @ 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.2012-03-19
  • 0
    @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.2012-03-19
  • 1
    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.2012-03-19
  • 0
    Where are you getting this definition? The definition I have seen is that $C=1$ and the power $r$ in $|x_{k}|\thicksim k^{-r}$ is called the compressibility of $x$. The larger $r$ the closer many of the entries of $x$ are to zero and so $x$ is more compressible.2012-03-20
  • 0
    Maybe the definition at the following site will help http://theproofisinthepudding.wordpress.com/2012/01/09/lecture1/2012-03-20
  • 0
    I think YohBS has the right idea. Perhaps this is a case of engineers not making careful definitions (by the standards of pure math).2012-10-27

2 Answers 2