1
$\begingroup$

I am trying to interpolate a function that is noisy, but I know with a high amount of certainty about a third of the points in the series. I am trying to estimate the smooth mean of the signal via a Reproducing Kernel Hilbert Space.

$m(t) = \sum_{i=0}^N\alpha_iK(t, t_i)$ where $m(t)$ is the mean of my signal($S$(t)) at time t.

I've been trying to use quadratic programming to solve the optimization problem of estimating the smoothest ($L_2$ regularization) mean of the signal via the following equations:

Minimize $a^t(K^tK)a$ subject to some constraints, where $K$ is a matrix of size $(T, N)$, and $a$ is a vector in $R^N$.

My questions are as follows:

  • When I run this optimization it smooths the signal a little bit from the least squares estimate, but then usually around 10 iterations into the optimization I get an error, "Terminated (singular KKT matrix)." What could be the possible causes of what I am seeing? An example of the output vs. the target is below.
  • Am I understanding the math of the RKHS properly? That one can estimate a function without including any of that function in the above problem? Note that there is no $S(t)$ in the optimization or the $m(t)$ equation.

Things I have tried:

  • I've made sure that I have no redundant constraints.
  • I've tried all different ways of normalizing the matrices.

An Example Ouput of CVXOPT (qp optimizer):

pcost       dcost       gap    pres   dres
0.0000e+00 -2.3939e+02  9e+01  1e+00  2e-16
5.8362e+00 -2.3144e+02  1e+02  9e-01  3e-15
7.6341e+01 -2.6186e+02  4e+02  8e-01  3e-14
5.6698e+02 -3.8453e+02  1e+03  5e-01  3e-13
1.7792e+03  1.0383e+03  1e+03  1e-01  8e-12
2.1835e+03  2.1503e+03  5e+01  3e-03  1e-11
2.1956e+03  2.1943e+03  2e+00  9e-05  3e-13
2.1957e+03  2.1957e+03  6e-02  1e-06  5e-13
2.1957e+03  2.1957e+03  8e-04  1e-08  3e-12
2.1957e+03  2.1957e+03  8e-06  1e-10  2e-12
2.1957e+03  2.1957e+03  8e-08  1e-12  3e-12
2.1957e+03  2.1957e+03  8e-10  1e-14  1e-12
2.1957e+03  2.1957e+03  8e-12  2e-16  4e-12
Terminated (singular KKT matrix).

Output Example

$\endgroup$

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.