Suppose I have a vector $x\in \mathbb{R}^D$ and a matrix $U\in\mathbb{R}^{m\times D}$. I would like to solve the following nonnegative least squares optimization problem:
$a = \text{argmin}_{y\in \mathbb{R}^m} ||x-y^TU ||_2^2 \text{ subject to: } y_i\geq 0\text{ for } i=1,2, \dots, m $
One of the more popular algorithms for solving this task is FNNLSa, which comes from the following paper:
Bro, R., & De Jong, S. (1997). A fast non‐negativity‐constrained least squares algorithm. Journal of Chemometrics: A Journal of the Chemometrics Society, 11(5), 393-401. (Link)
I am interested in the computational complexity of this algorithm (or a worst-case estimate for nonnegative least square solvers in general). Thank you very much.