5

Let $v\in \mathbb{R}^{n}$ be the vector of ones, $v=(1,1,1,\cdots,1).$

I need an orthogonal basis for the orthogonal complement $v^{\perp}$, the space of all vectors orthogonal to $v$. Of course, one can solve for such a basis using Gram-Schmidt, but I have an extra requirement: that the basis vectors are sparse.

Is there a standard such basis? I can start writing down basis vectors in an ad-hoc way, e.g.

\begin{align*} b_1 &= (1, -1, 0, 0, \cdots)\\ b_2 &= (0, 0, 1, -1, \cdots) \end{align*}

but obviously this pattern runs out after $n/2$ vectors.

user7530
  • 49,280

3 Answers3

4

You can get pretty close with vectors with four nonzero components,

$$\pmatrix{1&1&1&1&1&1&1&1&1&1&1&1&1&1&1&1\cr1&1&-1&-1&0&0&0&0&0&0&0&0&0&0&0&0\cr1&-1&1&-1&0&0&0&0&0&0&0&0&0&0&0&0\cr-1&1&1&-1&0&0&0&0&0&0&0&0&0&0&0&0\cr0&0&0&0&1&1&-1&-1&0&0&0&0&0&0&0&0\cr0&0&0&0&1&-1&1&-1&0&0&0&0&0&0&0&0\cr0&0&0&0&-1&1&1&-1&0&0&0&0&0&0&0&0\cr0&0&0&0&0&0&0&0&1&1&-1&-1&0&0&0&0\cr0&0&0&0&0&0&0&0&1&-1&1&-1&0&0&0&0\cr0&0&0&0&0&0&0&0&-1&1&1&-1&0&0&0&0\cr0&0&0&0&0&0&0&0&0&0&0&0&1&1&-1&-1\cr0&0&0&0&0&0&0&0&0&0&0&0&1&-1&1&-1\cr0&0&0&0&0&0&0&0&0&0&0&0&-1&1&1&-1\cr}$$

gets you 12 vectors where you want 15, but I'm not sure how sparse you can make those other three vectors you'd want.

Gerry Myerson
  • 179,216
3

I am not sure how good this approach might work for your problem. But maybe you can give it a shot. Let us try viewing your problem as an optimization problem. Then what you require is a matrix $X$ of dimensions $n\times n-1$ whose columns are orthogonal to each other and also orthogonal to the all-ones vectors. Let's call the all-ones vector as $a$. At the same time you want this matrix as sparse as possible. Then your problem can be written as $$\min_{X\in\mathbb{R}^{n\times n-1}}~||X||_0 \\s.t.~~X^TX=I ~\\~~~~X^Ta=0$$The first constraint is referred to as the orthogonality constraint. $||X||_0$ is the $L_0$ norm of the matrix $X$ (simply put the number of non-zero entries). Thus, you are trying to find a matrix such that it's columns are orthogonal to each other and also is orthogonal to a given vector $a$. Now, the objective is non-convex (and non-differentiable) and so is the orthogonality constraint.

What is typically followed in practice then is that you can relax the $L_0$ norm to $L_1$ norm. Then objective becomes convex and differentiable. Also, the second constraint is already convex. Now, this belongs to the category of problems typically referred to as optimization with orthogonality constraints. There is already lot of research in this which you can google and find out. One such paper is here. Note that this is more of a universal approach and doesn't take into account about the fact that $a$ is a all-ones vector which is what some other answers are doing and thus might be more effective.

dineshdileep
  • 8,887
0

This is probably not the sparsest one, but it's quite sparse and has other benefits: The Haar wavelet basis. One of its elements is the constant vector and the full $n\times n$ about $\log(n)$ entries (I think). Drawback: Only exists for $n=2^k$…

The $n=8$ case looks like this (without normalization of the columns): $$ \begin{bmatrix} 1 & 1 & 0 & 0 & 0& 1 & 0 & 1\\ 1 & -1 & 0 & 0 & 0& 1 & 0 & 1\\ 1 & 0 & 1 & 0 & 0 & -1 & 0 & 1\\ 1 & 0 & -1 & 0 & 0 & -1 & 0 & 1\\ 1 & 0 & 0 & 1 & 0 & 0 & 1 & -1\\ 1 & 0 & 0 & -1 & 0 & 0 & 1 & -1\\ 1 & 0 & 0 & 0 & 1 & 0 & -1 & -1\\ 1 & 0 & 0 & 0 & -1 & 0 & -1 & -1 \end{bmatrix} $$

Dirk
  • 11,680