<p>I know virtually noting about Fourier Analysis and I'd like to know whether it's worth to learn this topic for my problem.</p>

<p>My problem is: Given vectors $h_1,\cdots,h_k\in\{+1,-1\}^n$ where $k &lt; n$, decide whether there exists another vector $x\in\{+1,-1\}^n$ that is orthogonal to all of $h_1,\cdots,h_k$.</p>

<p>I think I may formulate my problem with the help of a quadratic function $f(x) = x^T\left(\sum_{i=1}^k h_i h_i^T\right)x$ to have a condition that </p>

<blockquote>
  <p>$f(x) = 0$ if and only if $x$ is orthogonal to $h_1,\cdots,h_k$.</p>
</blockquote>

<p>As the desired function is a boolean function that $f:\{+1,-1\}^n\to\mathbb{R}$, it may be uniquely represented by a certain <a href="http://www.contrib.andrew.cmu.edu/~ryanod/?p=207" rel="nofollow">Fourier expansion</a> . Then my job is to check whether this function has zero Fourier coefficients or not.</p>

<p>I know there can be $2^n$ Fourier coefficients. And it may be impossible to check whether a function has a Fourier expansion with zero coefficients. Does this approach make sense? Is there any reference / related work on this kind of problem?</p>

CC BY-SA 3.0
2014-03-07T17:17:13.680Z
think it would help to look at cases where there is no orthogonal vector in $\{+1,-1\}^n$...? what implies that? maybe some possibility to reduce to some problem on bitvectors instead of $\mathbb{R}$?
vzn
CC BY-SA 3.0
2014-03-09T03:00:32.310Z
You might want to take a look at this previous cstheory question: http://cstheory.stackexchange.com/questions/20285/testing-boolean-vectors-orthogonality-with-fast-query-time
apw
CC BY-SA 3.0
2014-03-09T04:54:23.630Z
The Fourier coefficients of $f$ are all of degree $2$, and are given by the entries of the symmetric matrix $\sum{h_i h_i^T}$. Without the constraints $k < n$ (and with $k = O(n)$) this is NP-hard to approximate in a very strong sense, see http://paul.rutgers.edu/~anikolov/Files/charikarM.pdf
Sasho Nikolov
<boolean-functions><fourier-analysis>
Fourier Analysis on checking whether there exists a vector in hypercube orthogonal to a set of vectors?
Federico Magallanez
# Fourier Analysis on checking whether there exists a vector in hypercube orthogonal to a set of vectors?

(Asked by: username_0 on 2014-03-06)

I know virtually noting about Fourier Analysis and I'd like to know whether it's worth to learn this topic for my problem.

My problem is: Given vectors $h\_1,\cdots,h\_k\in\{+1,-1\}^n$ where $k < n$, decide whether there exists another vector $x\in\{+1,-1\}^n$ that is orthogonal to all of $h\_1,\cdots,h\_k$.

I think I may formulate my problem with the help of a quadratic function $f(x) = x^T\left(\sum\_{i=1}^k h\_i h\_i^T\right)x$ to have a condition that

> $f(x) = 0$ if and only if $x$ is orthogonal to $h\_1,\cdots,h\_k$.

As the desired function is a boolean function that $f:\{+1,-1\}^n\to\mathbb{R}$, it may be uniquely represented by a certain [Fourier expansion](http://www.contrib.andrew.cmu.edu/~ryanod/?p=207) . Then my job is to check whether this function has zero Fourier coefficients or not.

I know there can be $2^n$ Fourier coefficients. And it may be impossible to check whether a function has a Fourier expansion with zero coefficients. Does this approach make sense? Is there any reference / related work on this kind of problem?

**Tags:** boolean-functions, fourier-analysis

> **Comments:**
> **username_1**: think it would help to look at cases where there is no orthogonal vector in $\{+1,-1\}^n$...? what implies that? maybe some possibility to reduce to some problem on bitvectors instead of $\mathbb{R}$?  
> **username_2**: You might want to take a look at this previous cstheory question: http://cstheory.stackexchange.com/questions/20285/testing-boolean-vectors-orthogonality-with-fast-query-time  
> **username_3**: The Fourier coefficients of $f$ are all of degree $2$, and are given by the entries of the symmetric matrix $\sum{h_i h_i^T}$. Without the constraints $k < n$ (and with $k = O(n)$) this is NP-hard to approximate in a very strong sense, see http://paul.rutgers.edu/~anikolov/Files/charikarM.pdf  

---

## 0 answers

