Consider a known rectangular box $\Omega \in \mathbb{R}^d$, and $x \in \mathbb{R}^d$ a vector. I would like to determine an inexpensive way to compute $y^* \in \Omega$, such that $$y^* = \arg \min_{y \in \Omega}{(||x-y||_2)}$$.
I need to compute it with $d$ potentially very large, is there a way to do it with a time complexity of $\mathcal{O}(d)$ ? Any computation method is welcome anyway.
First, we can write the box as a cartesian product of intervals, $\prod_{i=1}^d [a_i, b_i]$. We also write $x = (x_1, ..,x_d)$ and $y^* = (y^*_1, ..., y^*_d) $. My first intuition, looking at a 2d rectangle, is that if $x_i \in [a_i,b_i]$ then $y_i^* = x_i$.
When $x_i \notin [a_i,b_i]$ then $y_i^* = \arg \min_{a_i,b_i}{(||x_i-a_i||_2,||x_i-b_i||_2)}$.
Does that sounds correct to you ? It's only an intuition and I did not work on a proof.
Your intuition is sound. Can you see why?
Hint: Observe that minimizing ${\lVert x - y\rVert}_2$ is the same as minimizing ${\lVert x - y\rVert}_2^2$. In this format, it should be easier to see you can minimize the square difference of each coordinate independently.