Q: Non-negative least squares: how bad is this heuristic? The non-negative least squares (NNLS) optimization problem is as follows: for given $A \in \mathbb{R}^{n \times m}$, $y \in \mathbb{R}^n$, find $x \in \mathbb{R}_{\geq 0}^m$ that minimizes $||Ax - y||_2$. There are several algorithms available, e.g. this one. They appear to be significantly more sophisticated compared to the ordinary least squares (OLS) solution.
Consider, however, the following simple heuristic:

*

*initialize the set $R = [m]$,

*find $x$ — a solution to OLS, applied to $A$ constrained to the latent subspace spanned by indices in $R$,

*if $x$ is non-negative, return it,

*otherwise, banish indices of all negative entries in $x$ from $R$, and return to step 2.

Let $\varepsilon(A, y) = \min_{x \in \mathbb{R}_{\geq 0}^m} ||Ax - y||_2$ — the true minimum error norm. Also, let $\varepsilon'(A, y) = ||Ax'(A, y) - y||_2$, where $x'(A, y)$ is the output of the procedure above. Define $t(m) = \inf\{t \mid \varepsilon'(A, y) \leq t \cdot \varepsilon(A, y)~\forall A, y \}$, where $A, y$ range over all feasible inputs with latent space of dimension $m$ (regardless of the row count). We deem an instance feasible if all principal minors of $A^T A$ are non-zero (that is, the OLS solution is applicable to any restriction of the latent space without encountering an ill-defined inverse). Stability issues can be ignored.
Question(s).

*

*Does $t(m)$ exist for all $m$?

*If the answer to 1 is "yes", is $t(m) \equiv 1$ (that is, is the heuristic the precise solution (probably not))?

*If the answer to 2 is "no", what's the best upper bound for $t(m)$ as a function of $m$?

I also welcome comments about good practical approaches to NNLS.
