1
$\begingroup$

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

  1. The center of the hypercube is $\vec{c} = \frac{1}{2}\vec{1}$.
  2. Find $\vec{u} = \textit{proj}_{O}(\vec{c})$
  3. If $\vec{u}$ is within the hypercube, return true.
  4. Otherwise, find corner $\vec{v}$ of the hypercube that is closest to $\vec{u}$
  5. Find $\vec{w} = \textit{proj}_{O}(\vec{v})$
  6. If $\vec{w}$ is within the hypercube, return true.
  7. Otherwise, return false.

Question

Is the method correct? Is there a faster way?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.