Find the Closest Vector to a Given Vector from a Given Set Defined by Set of Multiplications

Question

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.

Answer 1

I would got with one of the approaches (They are not closed form solutions but might be good enough):

1. Try estimating $ {u}_{i} $ by looking at the vector $ \left[ {y}_{1}, {y}_{2} / {y}_{1}, {y}_{3} / {y}_{2}, \ldots, {y}_{n} / {y}_{n - 1} \right] $ then taking the nearest value out of $ \left\{ 0.8, 1.3 \right\} $.
2. Apply the $ \ln \left( \cdot \right) $ on each element of $ \boldsymbol{y} $. Then each element becomes sum of $ {u}_{i} $ which means you can solve a problem of the form $ A u = \ln \left( y \right) $ (Pay attention to $ A $ as it is only 1 and 0 in a convolution like form). From the estimated $ \boldsymbol{u} $ you may build $ \boldsymbol{x} $.