Here's a puzzle. I'm looking for ideas on how to research solutions.
Given:
- Secret $n\times 1$ vector $x$
- Public $m\times n$ matrix $B$ with $m \ll n$
- (assume $B$ has rank $m$)
- Public product $b = B \cdot x$
In general, $x$ cannot be determined from $b$ and $B$ since $x$ has more elements than $B$ has rank.
Now, assume it is known that $x$ has at most $k$ non-zero elements, where $k \ll m$, but it is not known which elements are nonzero. For instance, if $k=1$, then $b$ is a scalar multiple of one column of $B$.
How would I go about determining $x$? Do any standard optimization techniques come to mind?
The typical way to estimate $x$ would be to minimize $\| x \|_1$ subject to the constraint that $Bx = b$. This optimization problem is known as the "basis pursuit" problem.
(We would prefer to minimize the number of nonzero components of $x$ subject to the constraint that $Bx = b$, but that is a nonconvex problem. Penalizing the $\ell_1$ norm of $x$ does a good job of promoting sparsity, and gives us a convex problem for which very efficient algorithms are available.)