1
$\begingroup$

We have the following non-convex optimization problem in $t \times m$ matrix $N$

$$\begin{array}{ll} \text{minimize} & \|W - N^{T}H N \|_F\\ \text{subject to} & N \geq 0\end{array}$$

where $W$ and $H$ are given symmetric, non-negative matrices of sizes $m \times m$ and $t \times t$, respectively. $H$ is also Toeplitz and positive semidefinite.

$$H = \begin{bmatrix} 2a_{1} & a_{2} & a_{3} \dots &a_{t} \\ a_{2} & 2a_{1} & \dots &a_{t-1} \\ \vdots & \vdots & \ddots & \vdots \\ a_{t} & a_{t-1} & \dots &2a_{1} \end{bmatrix}$$

where $a_{1}$ > $a_{2}$ > $\cdots$ > $a_{t}$.

Any suggestions for this problem? Thanks a lot.

$\endgroup$
  • 1
    $\begingroup$ Are you looking for an exact solution (that might take exponential time)? Some kind of fast heuristic? How big are $T$ and $M$? (tens, hundreds, thousands, millions, billions)? $\endgroup$ – Brian Borchers May 6 '18 at 1:32
  • $\begingroup$ Yes, I am looking for the exact solution. T could be thousands and M could be hundreds. Do you have any suggestions? Any website link or paper link could be very useful. Thank you very much! $\endgroup$ – Jin May 6 '18 at 1:35
  • 1
    $\begingroup$ Is $H$ positive semi-definite or can it be any symmetric matrix? $\endgroup$ – VHarisop May 6 '18 at 1:42
  • $\begingroup$ @VHarisop Thanks for helping me modify my problem, I also attach the additional information. So, assume that H is positive semi-definite, what will the optimization be? $\endgroup$ – Jin May 6 '18 at 18:02
1
$\begingroup$

After transforming the problem to

$\min_{N} \| W- N^{T}HN \|_{F}^{2}$

$N \geq 0$

you've got a problem with nonnegativity constraints and quartic polynomial objective function. This can be minimized to any desired tolerance by branch and bound methods, but these are exponential time algorithms, and with $T$ in the thousands and $M$ in the hundreds, this is most likely to be impractical.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.