We have: $A \in \mathbb{R}^{n \times m}$ with independent columns, $y \in \mathbb{R}^n$. Moreover, $n \gg m$.
Consider the following problem, where the inequality is elementwise:
$$x^{\star} := \arg\min_x \| Ax - y \|_2 \,\, \text{subject to} \,\, Ax \leq y$$
Is it possible to compute $x^{\star}$ by an algorithm of time complexity polynomial in $m$ and space complexity $O(m^3)$ in the following sense:
- Read the matrix $A$ row by row and the vector $y$ element by element, constructing objects of size $O(m^3)$ on the go.
- Apply some algorithm polynomial in $m$ to the constructed objects, computing $x^\star$.