how do you know if your matrix is sparse after sparsifying transform?

Question

To successfully compress the data using Compressive Sensing method, I need to have sparse vector, theoretically a vector is sparse if the entries of the vector has many zero or nearly zero. My question is how do you determined the maximum value of the nearly zero?

I tried it to make sparse matrix on Matlab. Let say I have 64 data which is a dense vector. After I tried to make my vector sparse using FFT I took the absolute value from it (I believe it's easier to identified the zero or nearly zero entries). My original value has minimum value of 1 and maximum value of 26 my sparse value has minimum value 7.3245 and maximum value of 602. based on my sparse vector, I don't think there is an entry it's nearly zero

Answer 1

If you can't find anything in the literature about a threshold, you can develop your own with the following procedure:

1. Generate $$N=\frac{ln(1-M)}{R}$$ random matrices $\boldsymbol{A}$ that you are certain ares sparse using your current method. Here, $M$ is the margin of error and $R$ is the maximum error resolution to be able to detect. Let's assume values of $0.95$ and $10^{-6}$, respectively.
2. Create an array of thresholds $\boldsymbol{\gamma}$ you wish to test. For example, $\boldsymbol{\gamma}=0:R:1$.
3. Create a counter for detections $d$.
4. Apply the first $\gamma$ from step 2 to the first matrix generated in step 1. Check for sparcity. If the matrix is correctly found to be sparce, add $1$ to $d$. Repeat this for every matrix in $\boldsymbol{A}$.
5. Calculate the probability of detection as $P_d=\frac{d}{N}$. Store it in a new array $\boldsymbol{P_d}$. Reset $d$.
6. Repeat step 4 and step 5, iterating through the $\boldsymbol{\gamma}$ each time.
7. Plot $\boldsymbol{P_d}$ against $\boldsymbol{\gamma}$ to visually inspect that the receiver operating characteristics were computed correctly.
8. Compute $$J=\frac{\Sigma P_d}{\Sigma P_d+\Sigma(1-P_{fa})}-\frac{\Sigma(1-P_{d})}{\Sigma (1-P_{d})+\Sigma P_{fa})}-1$$ where $J$ is the optimal threshold (using Youden's J Statistic).

For further resources in this topic I would recommend reading Detection and Estimation Theory by Van Trees.