Efficiently removing projection to subspace without having an orthogonal basis

Question

I have a number of vectors $v_1, …, v_n$ and another vector $w$, that all are linearly independent, but not orthogonal. Let $V := \mathop{\text{span}}(v_1, …, v_n)$. I need to remove $w$’s projection to $V$ from $w$, i.e., I need to find the vector $\tilde{w}$ such that $\langle \tilde{w},v \rangle = 0 ~∀~ v∈ V$ and $w-\tilde{w} ∈ V$. I need to do this exactly once for a given $V$.

Note that the scalar product is not the canonical scalar product and has a higher cost than $n$. Touching the scalar product would be extremely tedious, so for the purpose of this question you can consider it a blackbox.

My best solution for this so far is to apply Gram–Schmidt orthonormalisation to the collection $v_1, …, v_n, w$, without normalising the last vector, which then is $\tilde{w}$. With other words, I first orthonormalise $v_1, …, v_n$ to $\hat{v}_1, …, \hat{v}_n$ and then separately remove $w$’s projections to $\hat{v}_1, …, \hat{v}_n$ to obtain $\tilde{w}$.

Doing this, I need to calculate $\frac{n(n-1)}{2}$ scalar products (or norms) just to orthonormalise $V$ as a prerequisite for the last step, which only involves $n$ scalar products. This feels like there could be some more efficient way to do this, but I cannot find one.

Answer 1

Converted to an answer from my comments to Jan's answer.

To fix dimensions and notation, let us say that $V$ is a $m\times n$ matrix with the vectors $v_i$ as columns.

As Jan notes, we have to compute $$ \tilde w = [I - V(V^TMV)^{-1}V^TM]w, $$ where $M$ is the symmetric $m\times m$ matrix associated to the scalar product.

If it were possible to solve this problem with $O(n)$ black-box calls to the scalar product $M$, like the OP asks, then it would mean that we can solve the version of the problem in which $M=I$ in $O(mn)$, since now each scalar product costs $O(m)$. This seems too much to ask for, since the usual algorithms to compute projections (QR, SVD, solving the normal equations $(V^TV)^{-1}V^Tw$ explicitly...) all cost $O(mn^2)$.

This answer is an amended and corrected version of the comments: in the comments I claim that computing the scalar product costs $O(m)$ for each matrix $M$, but on second thought this is not true in general. For $M=I$ it's fine, though.

Answer 2

What about simply computing the projection of $w$ along the complement of $V$? $$ \tilde w = [I - V(VV^T)^{-1}V^T]w, $$ where $V$ is the matrix that has the basis vectors of $V$ as columns. This $\tilde w$ has all the properties that you look for.

If you are in the non standard scalar product, then there is a symmetric positive matrix $M$ that induces this scalar product. In this case the projection reads $$ \tilde w = [I - V(V^TMV)^{-1}V^TM]w. $$

It is OK, if the scalar product is a black box. You only need it's realization.

EDIT: The costs are mainly in the solve with $(V^TMV)$. If CG is applied, there will be a number of scalar product evaluations needed that scales with $n^2$: $\mathcal O(n)$ evaluations times $\mathcal O(n)$ iterations. (read the comments)