# Questions tagged [compressed-sensing]

The tag has no usage guidance.

37 questions
Filter by
Sorted by
Tagged with
45 views

### Basis pursuit algorithms for exponentially large matrices?

Are there any efficient algorithms/heuristics for basis pursuit for exponentially large matrices? That is $\arg\min_x\lVert x \rVert_0$ subject to $y = Ax$, where $A$ is an exponentially large matrix ...
76 views

### On sparse $0/1$ linear equations solvable with compressed sensing

If you have a system of $m$ linearly independent equations in $n$ variables with domain $0/1$ and we know there is at least one solution with at most $d$ variables to be $1$ then if $m$ at least a ...
71 views

### Additional structures for sparse recovery

The problem of sparse recovery using $l_1$ minimization is well known. Using random Gaussian matrices, we are able to achieve recovery with high probability in $O(k\log(d/k)$ measurements. It is ...
208 views

108 views

### NP-Hardness of Underdetermined Systems over $F_2$ implies the same for $F_{p^q}$

Assume that the yes-no problem of whether $x' \in F_{p^q}^{n}$ is a minimal support solution for a consistent underdetermined system $Ax=b,$ $A \in F_{p^q}^{m \times n}, b \in F_{p^q}^n$ is an NP-hard ...
338 views

### psd condition for matrix completion

The nuclear norm minimization for the matrix completion problem is given by \begin{align} \textrm{minimize } \quad &\|X\|_{*}\\ \textrm{subject to } \quad & X_{ij}=M_{ij} \quad \forall (i,j)...
140 views