0
$\begingroup$

Question: Under which conditions on $A, B\in\mathbb{R}^{N\times N}$ is the function $f: \mathbb{R}^N\mapsto \mathbb{R}^N$,

$$f(v) = A[v]_+ + B[-v]_+$$

surjective? Here $[.]_+$ is an elementwise rectifier,

$$[x]_+ = \begin{cases} x &\mbox{if } x > 0, \\ 0 & \mbox{otherwise}. \end{cases} $$

Remarks: In the simple case that $B = 0$ the image of $f(v)$ is the conic hull $\operatorname{cone}(S)$ of $S = \left\{a_i \,|\, i=1, \dots, N\right\}$ where $a_i$ are the columns of $A$. Clearly, for square $A$ the conic hull can never span $\mathbb{R}^N$, and so $f$ is not surjective in that case. The addition of the second factor $B$ makes the whole problem more interesting. Observe that either a column $a_i$ or the corresponding column $b_i$ can be active at the same time, but not both. Then define $C_i = \left\{a_i, b_i\right\}$ and $M = C_1\times\dots\times C_N$ as the cartesian product of the column pairs. In this case the image of $f$ is the union of conic hulls over points in $M$, i. e.

$$\bigcup\limits_{m\in M} \operatorname{cone}\left(\left\{m_i \,|\, i=1, \dots, N\right\}\right).$$

In general it is an NP-hard problem to determine whether a union of cones covers a convex set $D$ [1], but the problem considered here exhibits much more structure. Ideally, I would like to infer conditions on $A$ and $B$ under which $f$ is surjective, i.e. under which the coverage of $\mathbb{R}^N$ is complete. Any hints or comments are much appreciated!

[1] On a cone covering problem, https://people.mpi-inf.mpg.de/~elbassio/pub/unionofcones.pdf

$\endgroup$
2
  • $\begingroup$ "Unison" --> "union"? $\endgroup$ Aug 7, 2015 at 19:21
  • 1
    $\begingroup$ Of course - double typo... $\endgroup$
    – Wieland
    Aug 7, 2015 at 19:36

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.