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.



Nonlinear low-rank approximation - corrected
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.


