1
$\begingroup$

I am dealing with a complicated optimization problem with two parameters $N, K$. Setting $K =$ constant and finding the minimum for different $N$'s lead to a set of function values. I can do this for $K = 2,3,\cdots,8$ and $N = 5,6,\cdots,40$. Larger $K$'s or $N$'s take more time to calculate (e.g. 1 hour).

I've plotted what I get (blue) and a lower bound (green) for it, which is described by $L(N,K) = \sqrt{\frac{N-K}{K(N-1)}}$

$K = 3$ enter image description here

$K = 4$ enter image description here

Any of these two are desired :

  1. An expression with respect to $(N,K)$ which best approximates the values I'm getting.

  2. A tighter lower bound (for larger $N$'s)

What methods do you suggest?

|improve this question
$\endgroup$
  • $\begingroup$ Exact or least-squares polynomial interpolation are some methods that come to mind, at least without seeing a representative dataset. $\endgroup$ – Jason R Sep 20 '13 at 12:03
  • $\begingroup$ It would be helpful if you give us the function you are trying to approximate. $\endgroup$ – jan Sep 20 '13 at 15:10
  • $\begingroup$ In case the only parameters involved are $N, K$ then you can fit the data any way you want (Least squares, 1-Norm minimization methods are a few widely used ones). $\endgroup$ – Sudarsan Sep 20 '13 at 18:24
  • $\begingroup$ This looks like the Welch bound problem (lower bound on the maximum magnitude of the aperiodic autocorrelation and cross-correlation functions of $K$ binary sequences of length $N$). Giving some context would have been helpful. $\endgroup$ – Dilip Sarwate Sep 21 '13 at 13:36
  • $\begingroup$ It is conjectured that the blue curves are the exact minimum of maximum magnitude of cross-correlation of all columns of DFT sub-matrices of size $K\times N$. I want to see to what extent this conjecture is true? So finding a tighter lower bound for it is so useful! Also there is another one By Levenstein which is tighter than Welch one for $N>K^2$. $\endgroup$ – Mahdi Khosravi Sep 21 '13 at 14:33

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.