Projection onto rotated box Does anyone know if there is an efficient way to find the projection of an arbitrary point $z$ onto a rotated box, i.e. onto the set $\Omega=\{x \mid a \leq Ux \leq b\}$ where $U$ is a unitary matrix?
A naive solution would first rotate $z$, which has a complexity $O(n^2)$, and then the problem reduces to projecting onto a non-rotated box, which can be solved in $O(n)$.
However, in my application (essentially proximal gradient descent) I would need to solve this subproblem a lot of times, and $n$ would be in the order of several millions. Thus $O(n^2)$ per call is not an affordable complexity. The value of $z$ would change among calls, but $a$, $b$ and $U$ would be the same for all calls. Hence, any way of exploiting the fact that $a$, $b$ and $U$ are constant which results in reduced complexity across calls for different values of $z$ would be extremely beneficial.
Is there a way to reduce the complexity of the naive approach or is $O(n^2)$ per call the best one can achieve for this projection problem?
 A: Suppose you want to rotate $k$ vectors at once.  Consider the matrix $M$ formed by concatenating these $k$ vectors (so $M$ is an $n\times k$ matrix, and each column of $M$ is one of the original vectors).  
Then we can rotate all $k$ vectors by computing the product
$$ UM $$
Naively, this would take $O(kn^2)$ steps.  There exist "fast" matrix multiplication algorithms for rectangular matrices; a nice treatment of that can be found in Francois Le Gall's "Faster Algorithms for Rectangular Matrix Multiplication".  The complexity depends on the size of $k$ relative to $n$.
For example, if $k=O(\sqrt{n})$, then the naive running time of $O(n^{2.5})$ could be improved to $O(n^{2.046681})$.
Of course, these results are only asymptotic; in real life, these algorithms would probably be totally inappropriate.
A: Not sure if this points in the right direction since I don't know enough context. It seems like you could in principle set $y= Ux$ and either work with the rotated variable all over the place or use "splitting", i.e. consider $y=Ux$ as a new equality constraint in your original problem. Whether one of this options is practical depends very much on the context.
