I am considering whether permuting the data $x^* \in \mathbb{R}^{n \times 1}$ using a permutation matrix $P \in \mathbb{R}^{n \times n}$ can enhance the recoverability of $x^*$ in sparse recovery.
I am examining a sparse recovery problem in which a high-dimensional sparse signal $x^*$ needs to be recovered from its low-dimensional observation $y = APx^* \in \mathbb{R}^{m \times 1}$, where $A \in \mathbb{R}^{m \times n}$ is the sensing matrix, and $P$ is the permutation matrix.
In this problem, $x^*$ can be recovered by solving the following optimization problem: $$ \min_x \|x\|_0, \text{ s.t. } y=APx. $$
I want to determine if a specific permutation matrix $P$ can introduce a particular structure to $x$, leading to more accurate recovery. Therefore, the problem can be formulated as follows: $$ \begin{aligned} & \min_{P} \|x(P)-x^*\|, \\ \text{where } & x(P) = \arg\min_{x} \|x\|_0, \\ & \text{ s.t. } y=APx. \end{aligned} $$
Empirically, permutating $x$ can introduce structure to $P x$ and facilitate data compression, e.g., permuting $x$ such that elements in $P x$ are in increasing order. Hence, I am curious if any research has been conducted on finding the optimal permutation for improved recovery. I have attempted some searches, but the closest topic I have found is unlabeled sensing.