5
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • $\begingroup$ 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}$? $\endgroup$ – vzn Mar 7 '14 at 17:17
  • $\begingroup$ You might want to take a look at this previous cstheory question: cstheory.stackexchange.com/questions/20285/… $\endgroup$ – apw Mar 9 '14 at 3:00
  • 1
    $\begingroup$ 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 paul.rutgers.edu/~anikolov/Files/charikarM.pdf $\endgroup$ – Sasho Nikolov Mar 9 '14 at 4:54

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.