MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $C$ be size $n \times n^{2}$. Let $B$ be size $2^{g(n)} \times n^{2}$ where $g(n) > n$.

There is only one $\mathcal{1}$ per row of $C$ and remaining entries of $C$ are $\mathcal{0}$. $B$ is arbitrary.

$B$ and $C$ are known.

Let $\mathbf{1_{m}}$ be all $\mathcal{1}$ vector of size $\mathcal{1} \times m$, $\forall m \in \mathbb{N}$.

Let $A$ be size $n \times 2^{g(n)}$ (with $i,j$th entry $a_{ij}$) that needs to be found on the conditions:

$(0)$ $AB = C$ (linear condition).

$(1)$ $\mathbf{1_{n}}AB\mathbf{1_{n^{2}}}' = n^{\frac{3}{2}}$ (linear condition).

$(2)$ $\|A\|_{F}^{2}$, the Frobenius norm of $A$ is minimized (quadratic objective).

$(3)$ $\|\mathbf{1_{n}}A\|_{2}^{2}$ is maximized (quadratic objective).

$(4)$ $\forall i,j$, $a_{ij} \in \mathcal{S}$ where $S$ is either $[-\mathcal{1},\mathcal{1}]$ or $[\mathcal{0},\mathcal{1}]$ (Relaxing $S^{n \times 2^{g(n)}}$ to a sphere enclosing a cube $\{-\mathcal{1},\mathcal{1}\}^{n \times 2^{g(n)}}$ or $\{\mathcal{0},\mathcal{1}\}^{n \times 2^{g(n)}}$ for both interval definitions of $S$ provides quadratic constraint).

Is there a way to get a good approximation (tight lower/upper bounds) of $\|\mathbf{1_{n}}A_{abs}\|_{0}$? for the Donoho $0$-norm $\|\mathbf{1_{n}}A_{abs}\|_{0}$ where $A_{abs}$ is $A$ but with all entries replaced by their absolute values?

Any reference for this problem would be of help?

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.