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


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.