# Find closest vector to a given vector from a particular set of vector

Let $x=\left(x_t\right)_{t=1}^n$ be a vector such that $$x_t = \prod_{i=1}^t u_i, \tag{1}$$ where each parameters $u_i$ can take any of two value $$u_i \in \left\{a,b \right\} = \left\{ 1.3, 0.8 \right\}.$$ Each vector $x$ represents a path in a binomial tree.

Given an arbitrary vector $y=\left(y_t\right)_{t=1}^n$, where each $y_t$ is in $\mathbb R^+$, how to solve the problem $$\min_{x \in X} \lVert y - x \rVert^2 = \sum_{t=1}^n \left(y_t - x_t \right)^2$$ where $X$ is the set of all possible vector of the form (1).
So, given a realization of the stock, find the closest binomial path.

The only way I see to solve this problem is to do Gram-Schmidt on $X$, and then project $y$ on the orthonormal basis found.
But, my $n$ is large, say $100$.
This induces $$\mathrm{cardinality} X = 2^{100},$$ so I don't think Gram-Schmidt is viable.

I would use least-square or Newton-Raphson, but the variable are not continuous.

-
I don't know how to find the closest $x$, but a reasonable solution may be obtainable with the following binary tree algorithm. Let $R(a,b)$ be the number of $1.3$-multiplications in the interval $a\le t \le b$. Note that $R(1,t)$ determines $y_t$. Choose $R(1,n)$ to minimize $|x_n-y_n|$. Then choose $R(1,n/2)$ to minimize $|x_{n/2}-y_{n/2}|$. Then choose $R(1,n/4)$ based on $y_{n/4}$ and choose $R(n/2+1,3n/4)$ based on $y_{3n/4}$. And so on. This works better if $n$ is a power of $2$, but you can always divide in halves approximately. – user127096 Mar 24 '14 at 0:19