1
$\begingroup$

I would like to state that this is related to a past question of mine which contained errors and now appears in the corrected form, with the erroneous one deleted and closed. In my research of linear algebra and optimization I have recently come across a problem related to the well-known low-rank optimization problem:

Given a constant matrix $X\in\mathbb{R}^{n \times n}$, $$\min_{A\in\mathbb{R}^{n\times k}, B\in\mathbb{R}^{k \times n}} \| X - A B \|_F$$

Where the norm is the Frobenius norm. I was considering this interesting possible extension:

Given a constant matrix $X\in\mathbb{R}^{n \times n}$, $$\min_{A\in\mathbb{R}^{n\times k}, B\in\mathbb{R}^{k \times n}} \| X - A \phi(B) \|_F$$ where $ \phi $ is a smooth convex function $ \phi : \mathbb{R}\to\mathbb{R} $ (a scalar function applied entrywise to the matrix argument).

Of course if $ \phi $ is linear the problem is quite easy, but when $\phi$ is non-linear things are more complicated and interesting. My question is, can I hope to find specific functions/families of nonlinear functions $\phi$ for which the problem is analytically solvable or approximated (by bounds or approximations of some kind)? I was thinking perhaps power series expansions can help or probability tricks of some sort, but I cannot really proceed. I was thinking in the direction where $ \phi(x)=\max{(x,0)} $ meaning entrywise positive part of the rectangular matrix $ B $. Also, can someone suggest an algorithm to solve this? I thank all helpers.

$\endgroup$
1
$\begingroup$

Since $\phi$ is a convex function, you can approximate it with linear functions with the maximum operator. The problem is then turned into a quadratic programming problem due to the Frobenius norm. If it is an $L_1$ norm, then it is a linear programming problem.

| cite | improve this answer | |
$\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.