1
$\begingroup$

Given an $k \times 1$ vector of height values $\mathbf{z}$ and an $k \times 1$ vector of weights $\mathbf{w}(x, y)$ at a location $(x, y)$, I am interested in the result of their dot product (linear combination of the heights): $$\mathbf{w}(x, y)^T \mathbf{z} = d$$

I can also collect weights at $N$ locations into a matrix $W$ of size $k \times N$ and compute: $$W^T \mathbf{z} = \mathbf{d}$$

For reasons explained below, I have reduced the dimensionality of $W$ using SVD: $$\widetilde{W} = U_r \ \text{diag}(s_r) V_r^T \approx W$$

Where $U_R$, $s_r$ and $V_r$ have been extracted from the decomposition $W = U \ \text{diag}(s) V^T$ to cover 99% of the sum of the Eigenvalues.

Without dimensionality reduction, since $V$ is a real unitary matrix, we have $V V^T = I$ and so: $$(W^T V) (V^T \mathbf{z}) = \mathbf{d}$$

Is it reasonable to expect the following? $$(W^T V_r) (V_r^T \mathbf{z}) \approx \mathbf{d}$$

If not, is there a way to carry out the dot product in the reduced space to get a good approximation of $\mathbf{d}$?


More context

In my case, the weights $\mathbf{w}(x, y)$ are expensive to evaluate, but I need to compute bounds on the values of $d$ over a small region of space. My intent was to precompute a bounding ellipsoid in $k$-dimensional space for the vectors $\mathbf{w}(x, y)$ in my region.
Then, as height vectors $\mathbf{z}$ become available, I can project the boundaries of the ellipsoid onto the vector to obtain bounds on the results of the dot product. This is pretty efficient, since there can be many height values but the weights remain the same.

However, it turned out that my weight matrix $W$ has low-rank, and so the resulting bounding ellipsoid was singular. Hence the idea to use dimensionality reduction on $W$ first, compute the bounding ellipsoid in reduced space, and the final dot product as well.

$\endgroup$
  • $\begingroup$ Do zero padding and keep the size same. In this case you will get something very close to $d$. Other way is to consider KL-decomposition. That is the best compression technique. $\endgroup$ – Seyhmus Güngören Jun 18 '17 at 1:26

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.