Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.