I am interested in solving the following equation in $t$,

\begin{equation} \| \boldsymbol{p} + \boldsymbol{D}^t \boldsymbol{q} \|^2 \approx \epsilon \,. \end{equation}

Here $\boldsymbol{p} \in \mathbb{R}^N$, $\boldsymbol{q} \in \mathbb{R}^N$, and $\boldsymbol{D}$ is a diagonal matrix, $\epsilon>0$ and $t$ is a positive integer.

The $\approx$ means the closest positive integer $t$ that can solve the equation. In other words, the problem can be defined as,

\begin{equation} t^*=\arg\min_{t \in \mathbb{N}} | \| \boldsymbol{p} + \boldsymbol{D}^t \boldsymbol{q} \|^2 - \epsilon |\,. \end{equation}

In scalar notation the problem is,

\begin{equation} t^*=\arg\min_{t \in \mathbb{N}} | \sum_{n=1}^N (p_n + d_n^t q_n)^2 - \epsilon |\,. \end{equation}

I believe a closed form solution does not exist, but I will be happy if I could solve,

\begin{equation} t^*=\arg\min_{t \in \mathbb{N}} | UB[\sum_{n=1}^N (p_n + d_n^t q_n)^2] - \epsilon |\,. \end{equation}

where $UB[.]$ means an upper bound. So the question really is about seeking a reasonably good upper bound on $\sum_{n=1}^N (p_n + d_n^t q_n)^2$ for which we can obtain a closed form expression for $t^*$.

Ideally, I do not want to make assumption about the signs (positive/negative) of $p_n$, $d_n$, and $q_n$.

Any idea would be highly appreciated.


  • 1
    $\begingroup$ Unless you are restricting $t$ to be integer, you'd better make an assumption about $d_n$ being non-negative. $\endgroup$ – Paul Sinclair Oct 12 '17 at 2:58
  • $\begingroup$ $t$ is indeed a positive integer. Thank you for point out. I added that to the original post. $\endgroup$ – Golabi Oct 12 '17 at 3:59
  • 1
    $\begingroup$ Which brings up another point: by varying $t, \| \boldsymbol{p} + \boldsymbol{D}^t \boldsymbol{q} \|^2 $ only takes on a countable number of values, so there are only countably many values of $\epsilon$ for which equality can ever hold. For all the other $\epsilon$, all you can do is the find the $t$ that comes closest. $\endgroup$ – Paul Sinclair Oct 12 '17 at 16:06
  • $\begingroup$ You are right! It is fine to find the $t$ that comes closest to solving the equation, i.e. $t^*=\arg\min_t |UB[||\boldsymbol{p}+\boldsymbol{D}^t\boldsymbol{q}\|] - \epsilon|$. I will add this comment to the original post. $\endgroup$ – Golabi Oct 12 '17 at 16:32

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.