2
$\begingroup$

Given the matrix $\mathbf{W} \in \mathbb{R}^{N \times N}$ and the vector $\mathbf{y} \in \{\pm 1\}^N$, how to solve

$$\min_{\mathbf{x}\in \{\pm 1\}^N} \left\| \operatorname{sign}(\mathbf{Wx}) - \mathbf{y} \right\|_2^2$$

where $\operatorname{sign}(\cdot)$ is applied elementwise to a vector?

I have tried $\mathbf{x} = \operatorname{sign}\left(\mathbf{W}^{-1}\mathbf{y}\right)$ and $\mathbf{x} = \operatorname{sign}\left(\mathbf{W}^{T}\mathbf{y}\right)$ but found they don't work well.

This optimization problem was formulated while reading literature on neural networks, namely, Hopfield networks.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ @RodrigodeAzevedo, re, note that bare \| doesn't indicate whether it is opening or closing, and so spaces poorly with \operatornamed operators. Consider, for example, $\|\operatorname{sign}(\cdot)\|$ \|\operatorname{sign}(\cdot)\| vs. $\lVert\operatorname{sign}(\cdot)\rVert$ \lVert\operatorname{sign}(\cdot)\rVert. I edited accordingly. This effect can also be accomplished with \left\| and \right\|, as you did in the body, but that can have a jarring effect: e.g., $\displaystyle\left\|a_{\frac1 2}\right\|$ is too big for many people. $\endgroup$
    – LSpice
    Commented Apr 16, 2023 at 18:35
  • $\begingroup$ Denoting the rows of $\mathbf{W}$ by $\mathbf{w}_1,\dots,\mathbf{w}_n$ and setting $\mathbf{v}_i:=y_i\mathbf{w}_i$, the problem turns into finding the largest $k$ with the property that the region of $\Bbb{R}^n$ described by $\langle v_{i_j},\mathbf{x}\rangle< 0$ ($i_1<\dots<i_k$) contains a point from $\{-1,1\}^n$. $\endgroup$
    – KhashF
    Commented Apr 16, 2023 at 20:30

0

Reset to default

You must log in to answer this question.