2
$\begingroup$

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
$\endgroup$
  • $\begingroup$ Where are your constraints? $\endgroup$ – Arnold Neumaier Oct 16 '12 at 13:22
  • $\begingroup$ 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)$ $\endgroup$ – Johan Löfberg Oct 16 '12 at 13:23
  • $\begingroup$ @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? $\endgroup$ – user189035 Oct 16 '12 at 13:41
  • $\begingroup$ 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. $\endgroup$ – Arnold Neumaier Oct 16 '12 at 15:30
  • $\begingroup$ @ArnoldNeumaier: ok i will (i tought that the "|" made it clear that x0 and x1 were given $\endgroup$ – user189035 Oct 16 '12 at 15:58
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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}$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ $k$ is an unconstrained scalar (or a $d$ vector with $k-1$ linear restrictions). I suspect there is a closed form. $\endgroup$ – user189035 Oct 16 '12 at 11:24
  • $\begingroup$ Yes there is, for example here at pag 6. Just substitute $\beta$ with $k$: google.com/… $\endgroup$ – Jugurtha Oct 16 '12 at 11:50
  • $\begingroup$ 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).... $\endgroup$ – user189035 Oct 16 '12 at 12:41
  • $\begingroup$ 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. $\endgroup$ – Jugurtha Oct 16 '12 at 14:17
  • $\begingroup$ 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) $\endgroup$ – Johan Löfberg Oct 16 '12 at 15:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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