Shapes
Let $C$ be the unit hypercube in $\mathbb{R}^{n}$.
Let $\vec{o}$ be a point in $\mathbb{R}^{n}$.
Let $B$ be a $n \times m$ matrix. The columns of $B$ are a set of linearly independent vectors in $\mathbb{R}^{n}$.
$m \le n$
$n$ is about 15 to 20.
Let $O$ be a $m$ dimensional coordinate with columns of $B$ as axes and $o$ as the origin.
Projection
- Given point $\vec{x}$ in $\mathbb{R}^{n}$.
- $\textit{proj}_{O}(\vec{x}) = B\vec{y}$ where vector $\vec{y}$ minimizes square norm of $B\vec{y} - (\vec{x} - \vec{o})$.
- That is solving a least square problem.
- $B\vec{y} = QQ^{T}\vec{x}$ where $B = QR$.
- QR factorization would need $2n^3$ flops. The two matrix-vector multiplications would each need $2n^{2}$ flops. (source).
Goal
I want to know if there exists any point ($\vec{z}$) within the hypercube such that $\vec{z} = \textit{proj}_{O}(\vec{z})$. That means $\vec{z}$ can be exactly represented by the coordinate system $O$.
Method
- The center of the hypercube is $\vec{c} = \frac{1}{2}\vec{1}$.
- Find $\vec{u} = \textit{proj}_{O}(\vec{c})$
- If $\vec{u}$ is within the hypercube, return true.
- Otherwise, find corner $\vec{v}$ of the hypercube that is closest to $\vec{u}$
- Find $\vec{w} = \textit{proj}_{O}(\vec{v})$
- If $\vec{w}$ is within the hypercube, return true.
- Otherwise, return false.
Question
Is the method correct? Is there a faster way?
