Least Squares Solution involving regularizer and weighted sum I have come across the following cost function:
$$
\text{min}_a\ \ (a^Tx^{(1)} -1)^2 + \sum_{j=1}^M \alpha_j (a^Tx_j^{(2)} +1)^2 + \frac{\lambda}{2}||a||^2
$$
This is a minimization over weight vector $a$. This is apparently related to Linear Discriminant Analysis, but I have never seen it in this form before.
The above problem can be found in the paper by H. T. Nguyen and A. W. M. Smeulders, "Robust tracking using foreground-background texture discrimination".
Here, the data set is:
$$
\{x^{(1)},1\}, \{x_j^{(2)},-1\}_{j=1}^{M}
$$
The closed form solution is
$$
a= \kappa[\lambda \boldsymbol{I} + \boldsymbol{B}]^{-1}[x^{(1)} -\bar{x}^{(2)}]
$$
Where
$$
\bar{x}^{(2)} = \sum_{j=1}^M\alpha_j x_j^{(2)}\\
\boldsymbol{B}=\sum_{j=1}^M\alpha_j[x_j^{(2)}-\bar{x}^{(2)}][x_j^{(2)}-\bar{x}^{(2)}]^T\\
\kappa = \frac{1}{1+\frac{1}{2}[x^{(1)} -\bar{x}^{(2)}]^T[\lambda \boldsymbol{I} + \boldsymbol{B}]^{-1}[x^{(1)} -\bar{x}^{(2)}]}
$$
This looks familiar like this should be a well known solution. But there appears to be alot of things at play to get the closed form solution. I am familiar with regularized least squares, but I can't derive the solution. Here is my attempt:
I will start without the regularizer.
$$
\text{min}_a\ \ (a^Tx^{(1)} -1)^2 + \sum_{j=1}^M \alpha_j (a^Tx_j^{(2)} +1)^2
$$
I rewrite the cost as
$$
\text{min}_a\ \ (a^Tx^{(1)} -1)^2 + || \tilde{X}a + \underline\alpha^2||^2
$$
Where $\tilde{X}$ is the matrix with the $j^{th}$ row $=[\alpha_j^2x_j^{(2)}]^T$.
Taking the derivative wrt $a$ and equating to zero,
$$
[x^{(1)}x^{(1)T} + \tilde{X}^T\tilde{X}]a = x^{(1)} - \tilde{X}^T\underline\alpha^2
$$
This already appears to be wrong as $\tilde{X}^T\underline\alpha^2 \ne \bar{x}^{(2)}$.
If anyone can help me understand the derivation, or  point me toward resources, or specific names of this type of least squares that would be helpful. Thank you.
 A: $\newcommand{\1}{\mathbf 1}$I'm going to rewrite the problem so that it's more directly amenable to derivatives. I'm also going to change the notation slightly just so I can type less. I'll use $z = x^{(1)}$ and then I'll drop the subscript $(2)$ from $x^{(2)}$. I'm also going to use $\lambda \|a\|^2$ instead of $\frac \lambda 2 \|a\|^2$ as the regularizer since all the other terms will give a factor of $2$ in the derivatives so this way that all cancels.
So, that said, I'm solving $\min_{a \in \mathbb R^p} f(a)$ where
$$
f(a) = (a^Tz - 1)^2 + \sum_{j=1}^m \alpha_j(a^Tx_j + 1)^2 + \lambda a^Ta.
$$
I want to rewrite this in a way that makes the derivatives easier. Letting $X$ be the $m\times p$ matrix with the $x_j$ as its rows, and letting $D_\alpha = \text{diag}(\alpha)$, I can write the middle term as
$$
(Xa + \1)^TD_\alpha(Xa + \1).
$$
Expanding the square in the first term I can overall write $f$ as
$$
f(a) = a^Tzz^Ta - 2a^Tz + 1 + (Xa + \1)^TD_\alpha(Xa + \1) + \lambda a^Ta \\
= a^Tzz^Ta - 2a^Tz + 1 + a^TX^TD_\alpha Xa + 2a^TX^TD_\alpha\1 + \1^TD_\alpha \1 + \lambda a^Ta \\
= 
a^T\left(\lambda I + zz^T +  X^TD_\alpha X\right)a - 2a^T\left(z - X^TD_\alpha\1\right) + 1 + \1^TD_\alpha \1.
$$
This shows that $f$ is a paraboloid and the quadratic term involves a positive definite matrix (guaranteed due to the regularizer) so this is convex and the root of the gradient is unique and the global minimizer.
That said, I can now easily compute
$$
\nabla f = 2\left(\lambda I + zz^T +  X^TD_\alpha X\right)a - 2\left(z - X^TD_\alpha\1\right) \stackrel{\text{set}}= \mathbf 0 \\
\implies \hat a = \left(\lambda I + zz^T +  X^TD_\alpha X\right)^{-1}\left(z - X^TD_\alpha\1\right).
$$
$X^TD_\alpha \1 = \bar x$ so my $z - X^TD_\alpha \1$ term matches the stated $x^{(1)} - \bar{x}^{(2)}$.

My solution disagrees with the rest of the stated solution though. I did some numerical experiments to see where the disagreement is and I think there may be an error with your stated solution (and it's not coming from me using $\lambda$ vs $\frac \lambda 2$ since I use $\lambda/2$ in the code here).
What my experiment shows is that when I numerically optimize this objective function it agrees with what I found, but both my solution and the numerical one disagree with the purported solution, and that solution also has a higher value for $f$.
rm(list=ls())
set.seed(123)

p <- 5   # dimension of `a`
m <- 10

z <- rnorm(p)
X <- matrix(rnorm(p*m), m, p)
alpha <- rgamma(m, 1.23)
lambda <- 2.55
tol <- 1e-15  # tolerance for numeric disagreement


# my solution, done using lambda/2 for agreement
Da <- diag(alpha)
ones <- rep(1, m)
a_hat_mine <- solve((lambda / 2) * diag(p) + z %*% t(z) + t(X) %*% Da %*% X) %*% (z - t(X) %*% Da %*% ones)


# their solution ~~~~~
# I'm deriving xbar2 in this way to check my math
xbar2 <- numeric(p)
for(j in 1:m) {xbar2 = xbar2 + alpha[j] * X[j,]}
stopifnot(sum((xbar2 - t(X) %*% Da %*% ones)^2) < tol)

B <- Reduce(`+`, lapply(1:m, function(j) alpha[j] * (X[j,] - xbar2) %*% t(X[j,] - xbar2)))
kappa <- as.numeric(
  1 / (1 + .5 * t(z - xbar2) %*% solve(lambda * diag(p) + B) %*% (z - xbar2))
)

a_hat_theirs <- kappa * solve(lambda * diag(p) + B) %*% (z - xbar2)

# numerically optimizing to see~~~~~~
 
f <- function(a, z, X, alpha, lambda) {
  (sum(a*z) - 1)^2 + 
    sum(sapply(1:nrow(X), function(j) alpha[j] * (sum(a * X[j,]) + 1)^2)) +
    lambda / 2 * sum(a^2)
}

# checking my linear algebra
f_linalg <- function(a, z, X, alpha, lambda) {
  m <- nrow(X); p <- ncol(X); Da <- diag(alpha); ones <- rep(1,m)
  as.numeric(
    t(a) %*% ((lambda/2) * diag(p) + z %*% t(z) + t(X) %*% Da %*% X) %*% a -
    2 * t(a) %*% (z - t(X) %*% Da %*% ones) +
    1 + sum(Da)
  )
}

a_tmp <- rnorm(p)
# good to go
stopifnot( abs(f(a_tmp, z, X, alpha, lambda) - f_linalg(a_tmp, z, X, alpha, lambda)) < tol)

# using `optim` to numerically optimize to check the calculus
opt <- optim(a_tmp, f, z=z, X=X, lambda=lambda, alpha=alpha, method='BFGS')
stopifnot(opt$convergence == 0)  # if it didn't converge i don't want to interpret
print(data.frame(mine = a_hat_mine, theirs = a_hat_theirs, opt = opt$par))
cat(
  f(a_hat_mine, z, X, alpha, lambda), f(a_hat_theirs, z, X, alpha, lambda), opt$value
)

