5

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 . 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?

Federico Magallanez
  • 591
  • 4
  • 8
  • 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 Mar 07 '14 at 17:17
  • 1
    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 Mar 09 '14 at 04:54
  • 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 Mar 09 '14 at 03:00

0 Answers0