Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Did you mean "Given $\mathbf{h}$..."? – user31373 Jun 10 '12 at 17:57
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. – user31373 Jun 11 '12 at 14:07
@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$. – Norbert Jun 11 '12 at 15:06
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. – user31373 Jun 11 '12 at 15:21
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. – joriki Jun 12 '12 at 2:12

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.