0
$\begingroup$

For a fixed $\mathbf{h}$ in a subset of $\mathbb{C}^m$ such that $\mathbf{h}(k)\neq 0$ for any $k=0,...,m-1$, how can I find

$\sup_{\mathbf{x}} \{ \| \mathbf{x} \|_1 \,\,\, \mathrm{ s.t. } \,\,\, \|\mathbf{h}\ast\mathbf{x}\|_1 \leq 1 \} $,

where $\mathbf{x} \in \{ \mathbf{y} \in \mathbb{C}^n : \mathbf{h} \ast \mathbf{y} = 0 \Leftrightarrow \mathbf{y} = 0 \} \subset \mathbb{C}^n$ is a vector subspace and $\ast$ denotes convolution? For this, convolution between two vectors $\mathbf{u}\in\mathbb{C}^p$ and $\mathbf{v}\in\mathbb{C}^q$ is the full discrete convolution of length $p+q-1$:

$\mathbf{z}(k) = \sum_{j=-\infty}^{\infty} {\mathbf{u}(j) \mathbf{v}(k-j)}$,

and for the purposes of computation $\mathbf{u}(j)=0 \; \mathrm{for} \; j\notin[0,p-1]$ and $\mathbf{v}(j)=0 \; \mathrm{for} \; j\notin[0,q-1]$

I would like to understand how to characterize the above for any and all $\mathbf{h}$, however, I'd be happy to start with special cases. For instance, if $\mathbf{h}=[-1,+1]$, then $\|\mathbf{h}\ast\mathbf{x}\|_1$ is the discrete Total Variation, which is well-studied in the literature, albeit from a functional analysis approach.

  • 0
    Did you mean "Given $\mathbf{h}$..."?2012-06-10
  • 0
    I'm not 100% sure that [functional-analysis] fits, but it was better than leaving the [norm] one on its own. If someone can review this change, I'd be glad.2012-06-10
  • 0
    I added (optimization). Tagging aside, I'd like to see the precise definition of convolution of two vectors.2012-06-10
  • 0
    If one of the coordinates of $h$ is zero, then this supremum if infinite2012-06-10
  • 0
    @Leonid: Yes. I meant given h. This has been fixed and hopefully the question is now more clear. Also, will the usual definition of convolution not work? $$(\mathbf{h}\ast\mathbf{x})(n) = \sum_{i=0}^{m-1}{\mathbf{h}(i) \cdot \mathbf{x}(n-i)}$$2012-06-11
  • 0
    @Norbert. I don't see why h having a zero-valued element makes the supremeum infinite. However, if so, then that is a constraint that needs to be added.In practical terms though, I would not expect any of the filters I am interested in to have a zero coefficient.2012-06-11
  • 1
    You could respond to comments by editing your original post. BTW Norbert made that comment because you did not define convolution in the original post, so he had to guess its meaning. Convolution of vectors isn't part of standard math curriculum. Personally, I still don't understand your formula for it. Is the convolution a single number or a vector? So far you defined just one number: $\mathbf{h*x}$ has $n$ in parenthesis, but $n$ is fixed, it's the dimension of the space where $\mathbf{x}$ lives.2012-06-11
  • 0
    @Leonid Sorry. I have been sloppy with the notation. The n in the convolution definition is meant as the index of the output vector and not the dimension.2012-06-11
  • 1
    @user33456 Let $h(1)=0$, then convolution with vector $(0,0,\ldots,10^{10^{10}})$ will give quite a big value for $\Vert x\Vert_1$ while $\Vert h*x\Vert_1$ is $0$.2012-06-11
  • 1
    Another example: if $h=[-1,1]$, as in the original post, then $\mathbf{h*x}=0$ for all constant vectors $\mathbf{x}$, hence the supremum of $\|\mathbf{x}\|$ is infinite... Unless I still don't interpret convolution correctly. What is the dimension of the vector $h*x$, i.e., what is the allowed range of index in $h*x$ in the formula.2012-06-11
  • 1
    Please edit all the information dispersed in the comments into the question to make it self-contained. People shouldn't have to read through the entire comments to understand the question.2012-06-12
  • 0
    @Leonid You make clear the point that $\mathbf{x}$ needs to be restricted to the subspace such that $\mathbf{h} \ast \mathbf{x} = 0 \Leftrightarrow \mathbf{x}=0$2012-06-12
  • 0
    @Norbert Thanks. I have added such a restriction to the question.2012-06-12

0 Answers 0