Tell me more ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.
up vote 2 down vote favorite

I was wondering whether there was a efficient procedure for solving constrained quadratic approximations of the form:

$$\underset{k\in \mathbb{R}}{\min}\;||x_i-kx_0||_2$$

for fixed values of $x_0,x_i\in \mathbb{R}^d$. This needs to be solved recursively for a large number of values of $x_i$ for fixed $x_0$ (so if there is a way to parametrize the solution in terms of $x_i$, that will be helpful).

Currently, I'm using an iterative algorithm (in R):

set.seed(123)
d<-100
n<-50
xi<-matrix(rnorm(n*d),n,d)
x0<-rnorm(d)
ff<-function(k,xi,x0,ll){
    crossprod(xi[ll,]-k*x0)
}
optimize(ff,lower=-1000,upper=1000,xi=xi,x0=x0,ll=13)$min
share|improve this question
Where are your constraints? – Arnold Neumaier Oct 16 '12 at 13:22
What is the constraint you are talking about? As it is written now, the optimal k follows by simply differentiating the expression, leading to $x_0^Tx_0/(x_0^Tx_i)$ – Johan Löfberg Oct 16 '12 at 13:23
@JohanLöfberg: thanks, this is the solution i was looking for [well, it's the inverse of the expression you wrote]-- can you post it as an answer? – user189035 Oct 16 '12 at 13:41
Ah, so both $x_0$ and the $x_i$ are fixed. You should revise your question accordingly, and remove the x-es from below the min sign. As it stands now, the formula is misleading. – Arnold Neumaier Oct 16 '12 at 15:30
@ArnoldNeumaier: ok i will (i tought that the "|" made it clear that x0 and x1 were given – user189035 Oct 16 '12 at 15:58
show 2 more comments

2 Answers

up vote 2 down vote accepted

By squaring the expression and differentiating w.r.t $k$, it follows that the unconstrained solution is $x_0^Tx_i/(x_0^Tx_0)$. If $k$ is bounded, the optimal solution is obtained by clipping the solution at the bound.

share|improve this answer
up vote 1 down vote

You can do it by Restricted Least Squares. If your constraints on $k$ are linear you should even have a closed form solution for $\hat{k}$.

share|improve this answer
$k$ is an unconstrained scalar (or a $d$ vector with $k-1$ linear restrictions). I suspect there is a closed form. – user189035 Oct 16 '12 at 11:24
Yes there is, for example here at pag 6. Just substitute $\beta$ with $k$: google.com/… – Jugurtha Oct 16 '12 at 11:50
no, it is not the same. In your example $\beta$ has the same # of component as $x$. In my example this is not the case (basically, you are ignoring the $k-1$ linear restriction).... – user189035 Oct 16 '12 at 12:41
Johan gives the right uncostrained solution for one $x_i$. The solution of the overall uncontrained problem is $\frac{x_0^T \bar{x}}{x^T_0 x_0}$, where $\bar{x}$ is the mean of all the $x_i$. Now the constraint must be added in. – Jugurtha Oct 16 '12 at 14:17
So if it is intended to be the sum of the squared norms in the objective, then the question has to be updated. As it is asked now, it asks for an efficient way to compute optimal k, for varying $x_i$, given that $x_0$ is fixed (Which is exploited by using the fact that $x_0^Tx_0$ is unchanged when solving for different $x_i$, i.e, one inner product can be eliminated) – Johan Löfberg Oct 16 '12 at 15:36
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.