1

Blind Joint MIMO Channel
Estimation and Decoding

arXiv:1802.01049v1 [eess.SP] 3 Feb 2018

Thomas R. Dean, Member, IEEE, Mary Wootters, Member, IEEE, and Andrea J. Goldsmith, Fellow, IEEE

Abstract—We propose a method for MIMO decoding when
channel state information (CSI) is unknown to both the transmitter and receiver. The proposed method requires some structure
in the transmitted signal for the decoding to be effective,
in particular that the underlying sources are drawn from a
hypercubic space. Our proposed technique fits a minimum
volume parallelepiped to the received samples. This problem
can be expressed as a non-convex optimization problem that
can be solved with high probability by gradient descent. Our
blind decoding algorithm can be used when communicating over
unknown MIMO wireless channels using either BPSK or MPAM
modulation. We apply our technique to jointly estimate MIMO
channel gain matrices and decode the underlying transmissions
with only knowledge of the transmitted constellation and without
the use of pilot symbols. Our results provide theoretical guarantees that the proposed algorithm is correct when applied to
small MIMO systems. Empirical results show small sample size
requirements, making this algorithm suitable for block-fading
channels with coherence times typically seen in practice. Our
approach has a loss of less than 3dB compared to zero-forcing
with perfect CSI, imposing a similar performance penalty as
space-time coding techniques without the loss of rate incurred
by those techniques.
Index Terms—MIMO, Multiuser detection, Blind source separation, Optimization

I. I NTRODUCTION
In this work we propose a method to blindly estimate MIMO
channels and decode the underlying transmissions. Given only
knowledge of the statistics of the channel gain matrix, the
constellation, and the channel noise, we exploit the geometry
of the constellation in order to jointly estimate the channel
gain matrix and decode the underlying data. More precisely,
we exploit the fact that the underlying constellation is often
hypercubic, i.e. forms a regular n-dimensional polytope with
mutually perpendicular sides, as is the case with BPSK or
MPAM modulation. The technique presented in this work can
also be applied to decoding and estimation in the SIMO MAC,
where channel gains are unknown at the receiver and there is
no coordination among transmitters.
In modern cellular systems, there is up to 15% transmission
overhead dedicated to performing channel estimation [1]. ImT. Dean is with the Department of Electrical Engineering, Stanford, CA
94305 USA (e-mail: trdean@stanford.edu).
M. Wootters is with the Department of Computer Science and the
Department of Electrical Engineering, Stanford, CA 94305 USA (e-mail:
marykw@stanford.edu).
A. Goldsmith is with the Department of Electrical Engineering, Stanford,
CA 94305 USA (email: andrea@ee.stanford.edu).
This work was presented in part in 2017 at IEEE Globecom in Singapore.
T. Dean is supported by the Fannie and John Hertz Foundation. This work
was supported in part by the NSF Center for Science of Information under
Grant CCF-0939370

proving channel estimation techniques, through, for example,
sparse dictionary learning [2], is an active area of research.
In practice, channel state information (CSI) is not always
needed to decode, but schemes that communicate without
CSI impose losses in rate or increased symbol error rates
[3]. Additionally, blind decoding schemes for MIMO systems
exist, but they are often inefficient in terms of complexity
or sample size requirements. This is discussed in more detail
in Section II. Obtaining accurate channel estimates is likely
to become more challenging in future generation wireless
systems, which will likely have both increased spatial diversity
and decreased coherence times [4]. Hence, improvements to
channel estimation, or to schemes that communicate without
CSI, have the potential to reduce overhead as well as improve
performance in current and future wireless systems.
This work is also motived by research in physical-layer
security. Several works have proposed keyless authentication
schemes that attempt to identify users based on properties of
the physical channel over which they communicate (see, for
example [5], or [6] for a survey). Since MIMO channels are
often well conditioned, and hence invertible, such schemes
require that CSI remains hidden from an adversary. Our work
shows that MIMO systems inherently leak CSI when the
underlying source is structured. From a security perspective,
this work implies that an eavesdropper need not have knowledge of pilot symbols nor any knowledge of the data being
transmitted in order to efficiently intercept and decode MIMO
communications. Any scheme that attempts to provide security
by hiding or obscuring pilot symbols will be insecure.
The blind decoding technique introduced in our work is motivated by a classical problem in convex optimization: fitting
a minimum volume ellipsoid (also known as the Löwner-John
ellipsoid) to a set of samples, as given in [7]. The method
proposed in this work fits samples to within a parallelepiped,
i.e. an n-dimensional polytope that has parallel and congruent
opposite faces, thereby recovering the inverse of the channel
gain matrix. In this work, we focus on MIMO systems that
have a small number of transmit antennas, specifically up to 8;
this choice of parameters captures nearly all MIMO systems
in use in wireless systems deployed today, for example see [8]
or [9].
We outline the major contributions of this work as follows:
• We introduce a novel (non-convex) optimization problem,
whose solutions capture those of the blind decoding
problem. Our formulation exploits the structure of the
underlying constellation so that solving this optimization
problem both estimates the channel gain matrix and
detects the underlying data symbols using far fewer sam-

2

ples of received symbols than previous blind decoding
techniques.
• Despite the fact that this problem is non-convex, we
give both theoretical and empirical results showing that
gradient descent is effective for solving the blind MIMO
decoding problem. More precisely, for general values of
n, we derive sufficient conditions to ensure that global
optima correspond to solutions of the blind decoding
problem for the case where BPSK is transmitted and
in the limit of infinite SNR. We further relate the blind
decoding problem to the Hadamard Maximal Determinant
problem. For n ≤ 4, we present necessary conditions so
that there are no spurious optima within the domain of
the optimization problem, implying that our approach will
always return a solution to the blind decoding problem.
Further, we provide evidence that formulating equivalent
necessary conditions for larger values of n is likely
intractable.
• For n ≤ 4, we give theoretical results that relate the
number of observed samples to the probability that our
method returns a correct solution to the blind decoding
problem. Our theoretical results nearly exactly match our
empirical results. Notice that n ≤ 4 captures the majority
of MIMO systems in use today.
• Although it seems difficult to provide theoretical evidence
that gradient descent performs well for large values of n,
we present empirical evidence suggesting that gradient
descent efficiently solves our non-convex optimization
problem and the blind decoding problem for values of
n as high as n = 15 and for values of M as large as
M = 16. Further, our empirical evidence shows that our
approach is robust in the presence of AWGN and that
decoding performance is comparable to known methods
that communicate over a MIMO channel without CSI
or with imperfect CSI. In particular, our blind method
outperforms existing non-blind methods when the CSI is
somewhat inaccurate.
The remainder of the paper is organized as follows. In Section II we provide a survey of techniques related to our work.
Section III describes our system model. Section IV outlines the
optimization problem that solves the blind decoding problem,
as well as algorithms that solve this optimization problem;
the theoretical performance of these algorithms is shown in
Section V. Section VI presents empirical results that support
the theory contained in Section V. Concluding remarks are
provided in Section VII. Proofs not contained in Section V
are found in the appendices.
II. R ELATED W ORK
The problem of joint blind channel estimation and decoding
is not new. For example, in [10], the authors apply MMSE
techniques to the blind decoding of MIMO problems over
small alphabets while simultaneously recovering the underlying channel gain matrix. The approach in [10] requires the
number of samples of received signals used by the algorithm
to grow linearly with constellation size, which is exponential
in n, the number of transmit antennas. The approach in [10]

only requires the underlying constellation to be discrete; however, for constellations that are also hypercubic, our approach
requires far fewer received samples than the approach of [10]
based on our simulation results.
In addition, blind decoding algorithms have previously been
applied to hypercubic sources. In [11], the authors present a
statistical learning algorithm that applies a modified version of
the Gram-Schmidt algorithm to an estimate of the covariance
matrix of the received signals to learn the channel gain matrix.
In a different setting, the authors in [12] learn a parallelepiped
from a covariance matrix by first orthogonalizing and then
recovering the rotation through higher order statistics. Our
method does not rely on the covariance matrix estimation and
our empirical results show that it requires fewer samples than
the techniques of [11] and [12], especially when the channel
gain matrix has a high condition number.
Blind source separation is the separation of a set of unknown
signals that are mixed through an unknown (typically linear)
process with no or little information about the mixing process
or the source signals. Several previous works have considered using blind source separation techniques for detection
of signals transmitted over unknown MIMO channels. Blind
source separation is typically accomplished through techniques
such as Principle Component Analysis (PCA), Independent
Component Analysis (ICA), or Non-Negative Matrix Factorization (NMF); see [13] for a survey of these techniques.
Other techniques exploit structure in the mixing process, for
example, [14] requires the mixing process to be a Toeplitz
matrix. Our technique differs from traditional blind source
separation as we obtain an estimate of the source signals by
learning the inverse of the mixing process rather than directly
estimating the source signals. As an output, our algorithm
produces both an estimate of the mixing process, i.e. the
channel gain matrix, and the source signal, i.e. the transmitted
symbols. Similarly, blind channel estimation techniques have
been studied, although most commonly for SISO channels.
See [15] or [16] for surveys on this topic. The approach
presented in this paper can be viewed outside the context of
communicating over an unknown MIMO channel as a general
technique that performs blind source separation of sources
mixed through an unknown, linear process.
Many techniques exist for communications over unknown
MIMO channels that do not rely on channel estimation. For
example, Space-Time Block Coding (STBC) was introduced
by Alamouti in [17] and formalized by Tarokh et al. in [3].
These techniques rely on coding transmissions using sets of
highly orthogonal codes so that the receiver can recover the
transmission without CSI. For the case of two transmitters,
rate one space-time block codes exist that impose a 3 dB
penalty in terms of SNR at the receiver. For larger numbers of
transmitters, rate one codes do not exist. Our techniques do not
require any coding at the transmitter and thus do not impose
any rate penalty. Numerical simulation shows the decoding
performance of our technique to be comparable to rate one
STBC methods.

3

III. S YSTEM M ODEL AND N OTATION
This work focuses on an n × n real-valued MIMO channel
with block fading and AWGN. In Section IV-C, we discuss
how this work can be extended to complex-valued channels
and channels with more receivers than transmitters. The inputoutput relation of this channel is characterized by:
y = Ax + e,

U

(1)

where x is drawn from a standard M -PAM or BPSK constellation; that is, X n for X = {2i − 1 − M : i = 1, 2, . . . , M }
or {−1, +1} respectively. The channel matrix A ∈ Rn×n
is drawn from a random distribution. For the simulations in
Section VI, we take A to be drawn with i.i.d. entries from
N (0, 1); however, our approach only requires A to be full rank
and thus A can be considered to be drawn from an arbitrary
distribution or entirely deterministic. The noise e ∈ Rn has
i.i.d. entries drawn from N (0, σ 2 ). We assume that A is blockfading, meaning that the value of A remains constant for some
coherence time, Tc , after which A is redrawn.
The receiver sees samples y1 , . . . , yk , as in (1). We assume
that the receiver knows the constellation X n but has no
knowledge of the points drawn from it, nor does it have any
knowledge of the matrix A.
Given messages x1 , . . . , xk ∈ Rn , we denote by X the
n × k-dimensional matrix formed by taking each symbol as
a column, and by Y the corresponding matrix with received
symbols as columns. Notice that we cannot hope to recover
A, X exactly. Indeed, since the constellation is invariant under
sign flips and permutations, we can always write AX =
ATT−1 X, where T is the product of a permutation matrix
and a diagonal matrix with entries ±1, and there is no way to
distinguish between the solutions (A, X) and (AT, T−1 X).
Such a matrix T is termed an admissible transform matrix
(ATM) in [10]. Thus, in this work, we aim to recover AT for
some ATM T.
While inevitable, these sign and permutation ambiguities
do not pose a huge problem in practice, and we ignore them
when comparing the results to MIMO decoding algorithms
with known CSI. We justify this approach as follows. First, in
the non-blind estimation case (i.e. where we have some control
over the transmission scheme and allow the transmitter to send
pilot symbols), assuming M > n, the permutation ambiguity
could be resolved by a single pilot symbol. Additionally, if we
consider the SIMO Multiple Access Channel, we can ignore
the issue of permutations of the received signals, for example
by assuming that identification occurs at a higher protocol
layer. Finally, we note that the sign ambiguity can easily be
resolved through differential modulation. In practice, it may
also be possible to resolve these ambiguities by examining
structure in the transmission scheme, present from either
protocol/framing data or structure in the underlying data. This
could prove to be difficult, however, if the data is encrypted
or compressed, or the underlying transmission protocol is
designed to thwart such analysis.
The notation bAe rounds elements of A to the nearest
element of X , and κ(A) denotes the condition number of
the matrix A, which is the ratio of the largest to the smallest

Fig. 1. The program given in (2)–(3) aims to find a linear transformation
U, that transforms a set of observed MIMO samples yi (left), such that the
resulting Uyi lie within the unit `∞ ball (right). By finding a U that has a
maximally-valued determinant, we are effectively finding a parallelepiped of
minimal volume that fits the observed samples.

singular value of A. ai denotes a column vector formed from
the ith column of A and a(j) denotes
  a row vector formed
from the jth row of A. We define nk q to be the Gaussian
binomial coefficient, which for any prime power q, counts
the number of k dimensional subspaces in a vector space
of dimension n over a finite field with q elements. For two
vector spaces X and Y, the notation X ≤ Y denotes “X is a
subspace of Y”. For any X ∈ Rn×n , vec(X) corresponds to
the length n2 column vector obtained by stacking the columns
of X in the usual ordering. Given a matrix X, the set cols(X)
denotes the set of vectors that comprise the columns of X.
IV. F ITTING A PARALLELEPIPED
Since each transmitted symbol xi is drawn from a hypercube, the values Axi are contained in an n-dimensional
parallelepiped. As yi = Axi +e, the received symbols yi will
lie in a slightly distorted parallelepiped. At reasonable SNR
levels, this distortion will be minimal. Thus, we formulate
the problem of blindly estimating the channel gain matrix as
fitting a parallelepiped to our observed symbols and express
this problem as an optimization problem. Given a set of k
samples of y1 , . . . , yk , consider the program:
maximize

log | det U|

(2)

subject to

kUyi k∞ ≤ M + c · σ, i = 1, . . . , k.

(3)

U

The domain of U is all n × n invertible matrices (not
necessarily symmetric or positive-semidefinite), meaning the
objective function is not necessarily convex. However, we will
show that if some condition on X is satisfied, then solutions
in the form U = TA−1 for some ATM T, correspond to
global optima to this problem; moreover, we show that these
are often the only optima and that gradient descent will find
them.
In this section, we present three separate algorithms. We
first present Algorithm 1, a simple algorithm using gradient
descent in the usual manner to solve (2)–(3). We demonstrate
in Section VI that, in practice, this algorithm is sufficient to
recover a solution to the blind decoding problem. In Section
IV-A, we present Algorithm 2, a slightly modified version of
Algorithm 1 that has a theoretical guarantee of correctness
under conditions given in Section V. Finally, in Section IV-B,
we include a description of the interior-point method which

4

allows us to use ordinary gradient descent to solve (2) while
remaining in the feasible region as given by (3).
Informally, by seeking to maximize the determinant of
U, subject to the `∞ -norm constraints, we are finding the
minimum volume parallelepiped that fits the observed samples.
Since U is the inverse of A, up to an ATM, maximizing U is
effectively finding the minimal U−1 which maps the `∞ -ball
to the observed samples. This is depicted in Figure 1. The
quantity c · σ present in (3) adds a margin to our constraint to
account for the presence of AWGN. In practice, values close to
c = 3 appear to be optimal as this captures 99% of the additive
Gaussian channel noise. More careful analysis is warranted to
understand how the performance of this algorithm is affected
by the value of c. More optimal methods of margining the
constraints of our optimization problem, such as the method
of ellipsoid peeling, given in [18], or other methods presented
in [19], may lead to further improvements in performance.
However, the simple margin presented here works well in
practice.
In order for (2)–(3) to be a meaningful problem, we require
Y to be full rank. If Y is not full rank, then the maximum
does not exist, formally shown in Proposition 1 below, which
is proven in Appendix A.
Proposition 1. If the matrix Y is not full rank, then (2)–(3)
is unbounded above. Conversely, if Y is full rank and k ≥ n,
then (2)–(3) is bounded above and feasible.
In our model, Y will be full rank with high probability
and thus, we assume that Y is always full rank and turn our
attention to solving (2)–(3). Maximizing the determinant of
a positive-semidefinite matrix is a classic problem in convex
optimization. Unfortunately, the matrix A is not necessarily
even symmetric and the problem is not convex. In order
to solve the problem we apply the MATLAB fmincon
solver that uses gradient descent to solve non-linear conic
optimization problems. The gradient of the problem given in
(2)–(3) has the following value (see, for example, [20]):
|
∇ (log | det U|) = U−1 .
(4)
Before we begin gradient descent, we check that Y is well
conditioned. As noted above, Y must be full rank for the
problem to make sense; however, if Y is full rank but poorly
conditioned, similar issues will arise and U may not invert the
channel. Thus, we return FAIL if κ(Y), the condition number
of Y, is larger than κmax . The gradient descent algorithm
requires a starting point as input, denoted as U(0) . We draw
this matrix uniformly at random over the set of all orthogonal
matrices, O(n), using the method described in [21]. We check
that this random U(0) in fact satisfies the constraints; if it does
not, we generate a new random matrix and scale the matrix
by a constant term until we find a suitable starting condition.
This is guaranteed to find a suitable U(0) in at most log2 κmax
iterations. The algorithm is summarized as Algorithm 1 below.
A. Modified Gradient Descent
In practice, Algorithm 1 works well and empirical results
show that it always returns solutions to (2)–(3) when k is

Algorithm 1 Fitting a Parallelepiped
Input: An n × k matrix of received samples Y.
Output: An estimate of the inverse of the channel gain matrix
U, and an estimate of the transmitted symbols X̂
1: if κ(Y) > κmax then
2:
return FAIL
3: end if
4: scale = 1;
5: Draw U(0) uniformly from O(n);
6: while |U(0) yi |∞ > 1 for any i do
7:
scale = scale * 2;
8:
Draw U(0) uniformly from O(n);
9:
U(0) = U(0) / scale;
10: end while
11: Run gradient descent over (2)–(3) starting at U(0) to find
an optimal value of U;
12: return U, X̂ = bUYe.

sufficiently large. However, the problem geometry, which is
studied in Section V, is non-convex and there is in fact a
small but non-zero probability that gradient descent will not
terminate at a global optimum. Moreover, in Section V, we
show that Algorithm 1 will only fail to find a global optima at
specific dimensions, and further that its probability of failure is
low. In this subsection, we present a modified gradient descent
algorithm, Algorithm 2, shown below, which is motivated by
the theory in Section V, where we show that all strict solutions
to (2)–(3) lie on vertices of the problem boundary. Algorithm
2 always terminates at a vertex of the feasible region, and it is
conjectured that, for general n, when k is slightly larger than
n, all non-singular vertices are global optima and solutions
to our channel estimation problem, implying that Algorithm 2
will always be correct.
Before describing Algorithm 2, we make the following
observations. The feasible region is bounded by 2kn halfs2
paces, forming an Rn dimensional polytope. We denote this
polytope as P. Notice that any row of U can be changed
without effecting whether or not the constraints on each of
the other rows of U are satisfied. Further, we say that U is a
vertex if it is a vertex of the n2 -dimensional polytope which
defines the problem boundary.
Algorithm 2 begins by choosing a starting position in
the same manner as Algorithm 1 and performing gradient
descent. In Section V it is shown that not only are all optima
contained on the problem boundary but also that the only
possible critical points on the problem boundary exist as
low-dimensional affine subspaces, along which the objective
function is constant valued. If gradient descent reaches such a
subspace, then Algorithm 2 continues by choosing a direction
on this subspace at random and moving in that direction until
the edge of the feasible region is reached. At this point,
the algorithm has either reached a vertex, in which case it
terminates, or gradient descent is continued from this point.
This process can be repeated until a vertex is reached.

5

Algorithm 2 Modified Gradient Descent
Input: An n × k matrix of received samples Y.
Output: An estimate of the inverse of the channel gain matrix
U, and an estimate of the transmitted symbols X̂
1: if κ(Y) > κmax then
2:
return FAIL
3: end if
4: Generate U(0) as described in Algorithm 1.
5: while U(i) is not at a vertex of the feasible region do
6:
Run gradient descent over (2)–(3) starting at U(i)
7:
for j in {0, . . . , n − 1} do
(i)
8:
if Uj is not at a vertex then
9:
Move in the direction of zero gradient to a vertex;
10:
end if
11:
end for
12:
U(i+1) = U(i) ; i++;
13: end while
14: return U, X̂ = bUYe.

B. Interior-Point Method
Both Algorithms 1 and 2 perform gradient descent on
an objective function subject to a convex set of constraints.
A naı̈ve implementation of gradient descent will not stay
within these constraints. There are many algorithms to perform
constrained optimization, for an overview, see [19].
For completeness, we propose using an interior-point
method with a standard logarithm barrier function to perform
the gradient descent step in both Algorithms 1 and 2. 1 This
method is attractive because it is simple to implement and has
reasonable computational complexity and numerical stability.
The results in Section VI are obtained using this method. We
formulate (2)–(3) into an unconstrained optimization function
by using the following barrier function:
B(U, µ) = f (U)−µ

k X
n
X

(log(1 − uj yi ) + log(1 + uj yi ))

i=1 j=1

(5)
The gradient of the barrier function can be computed using
the expression derived in (4). This is given by:
∇B(U, µ) = U−1

|

−µ

k X
n
X
i=1 j=1

+µ

k X
n
X
i=1 j=1

1
ej yi|
1 − uj yi
1
ej yi|
1 + uj yi

(6)

n
where ej is the
 j-th standard basis of R . Notice that this will
2
take O n k operations per step. The dominating operation
at each step is computing the product UY.

1 In Section V, we prove that optima of our problem lie on the boundary
of the feasible region. One may notice that the interior-point method is not
the most efficient algorithm given this fact. We base the analysis contained
in this paper on gradient descent because it makes the analysis tractable and
more easily understood. We defer to investigating more efficient algorithms
for this problem to be a topic of future research.

C. Further Extensions
The results in this paper readily extend to complex channels.
We can accomplish this by mapping an n × n-dimensional
complex channel to a 2n × 2n-dimensional real channel in
the usual manner. Note that this mapping imposes additional
constraints on our optimization problem. However, in Section
V, we derive the necessary and sufficient conditions for our
Algorithm 2 to return a correct solution to the blind decoding
problem. These results directly imply that we may simply
ignore these constraints and solve the 2n×2n-dimensional real
problem by using Algorithm 2 on (2)–(3). Since this approach
will return the correct channel gain matrix, up to a factor of a
2n-dimensional ATM, the amount of side information needed
to recover this ATM will be identical to the 2n-dimensional
real case. Whether or not the structure present in complex
channels can be utilized to create a more efficient algorithm
or reduce the required amount of side information is an open
question.
When there are more receivers than transmitters, the receiver
may still apply our algorithms by simply discarding all but
n received signals, but this is clearly suboptimal. Further
optimization of this case is a topic of future research. When
there are more transmitters than receivers then the nullspace of
the channel gain matrix will always be non-trivial and thus (2)–
(3) will be unbounded above. In this case, if we assume that
the transmit signals are uncoded and the channel gain matrix
is full rank, as is the case in this work, then detecting signals
transmitted over this channel is not a meaningful problem.
V. T HEORETICAL P ERFORMANCE G UARANTEES
Proving correctness of an algorithm that solves a nonconvex problem is often a difficult task. In this section, we lay
the groundwork for such an analysis by studying the noiseless
case. We provide guarantees on the correctness of Algorithm
2 for n = 2, 3, and 4. The motivation for studying Algorithm
2 over Algorithm 1 will become apparent in the following
subsections, as will the difficultly of proving the correctness
of our algorithms for more general or larger values of n. The
results in this section are strongly supported by the empirical
results shown in Section VI.
For the results in this section, we suppose σ = 0. We
also focus on the BPSK case, so xi ∈ {−1, +1}n . Deriving
matching theoretical results for larger M and in the presence
of noise remains an open problem; however, empirical results,
given in Section VI, show that Algorithms 1 and 2 still work
extremely well in these cases. As mentioned in Section IV
the problem (2)–(3) is a non-convex optimization problem,
and thus has several optima. Our analysis of gradient descent
applied to this problem will proceed as follows. First, we will
show in Section V-A that if n = k, then the optimization problem reduces to the Hadamard Maximal Determinant problem,
which asks for the maximum value of an n-dimensional matrix
whose entries are contained on the unit disk. We will use this
result to establish guiding intuition for the remainder of this
section. Additionally, we show that completely understanding
the problem geometry when n = k would solve the Hadamard
Maximal Determinant Problem; since the latter is considered

6

extremely difficult, this implies that a complete theoretical
analysis of our problem is likely out of reach.
In this section, we present a set of theorems that describe
when and why Algorithms 1 and 2 correctly solve the blind
decoding problem. The proofs of these theorems are contained
within the appendices of this work. The remainder of this
section is organized as follows. In Section V-B we will show
that Algorithm 2 will always terminate at a vertex of the
feasible region and that all strict optima of (2) lie on these
vertices. In Section V-C, we will state the necessary conditions
under which the set of global optima contains the solutions
to the blind decoding problem. Finally, we will conclude by
stating our theoretical guarantees; namely, necessary and sufficient conditions for Algorithm 2 to correctly solve the blind
decoding problem for the cases n = 2, 3, and 4. Additionally,
we conjecture about the performance of Algorithms 1 and 2
for larger n. Note that in practice, values of n ≤ 4 captures
nearly all MIMO systems that are currently in use today.
A. Reduction to the Hadamard Maximal Determinant Problem
We now proceed by showing the equivalence between (2)–
(3) and the Hadamard Maximal Determinant problem for the
case n = k. This problem is related to finding dimensions
at which Hadamard matrices exist. A Hadamard matrix is a
{−1, +1}-valued matrix with mutually orthogonal rows and
columns. Hadamard matrices are known to exist for n = 1, 2k ,
for all k ∈ N, and are conjectured to exist when n ≡ 0
mod 4.
Lemma 1. There exists an efficient algorithm that solves (2)–
(3) when n = k, if and only if there exists an efficient solution
to the Hadamard Maximal Determinant problem.
Proof. We show how, given an efficient algorithm to solve
(2)–(3), we can obtain solutions to the Hadamard Maximal
Determinant problem. Given an arbitrary, full-rank, set of k
samples of Y, by setting Ũ = UY, we arrive at the following
optimization problem, equivalent to (2)–(3)
maximize

log | det Ũ|

(7)

Ũ ∈ [−1, +1]n×n .

(8)

Ũ

subject to
Notice that for any value of n
max

w∈[−1,+1]n×n

| det W| =

max

w∈{−1,+1}n×n

| det W|.

(9)

This is because det W is linear in the columns of W and so
the maximum is obtained at a vertex of [−1, +1]n×n . Thus, we
may as well consider the maximum over {−1, +1}n instead
of [−1, +1]n . The optimal Ũ is the solution to the Hadamard
Maximal Determinant Problem.
This observation has many consequences. Many questions
regarding the Hadamard Maximal Determinant problem have
remained open since the problem was originally posed by
Hadamard in 1893 [22]. Even for moderately sized values of
n, the maximum value obtainable by (7) remains unknown
or unverified. However, our reduction holds only for n = k
and, empirically, the program given by (2)–(3) appears to

become easier as k grows relative to n. Roughly, as we add
constraints, we are removing vertices from the feasible region
in a way that leaves vertices that correspond to solutions. As
we show in the next subsection, Algorithm 2 is guaranteed
to terminate at a vertex, so, removing “bad” vertices increases
the likelihood that we terminate at a vertex that corresponds to
a solution to the blind decoding problem. The following facts
are consequences of this computational equivalence between
the Hadamard Maximal Determinant problem and the blind
decoding problem (see for example [23], [24], or [25]):
• For values of n such that Hadamard matrices exists, the
global optima to (7)–(8) is obtained if and only if Ũ is
a Hadamard matrix.
• The value of the objective function at vertices of the
problem boundary, which are the only strict optima of
(2)–(3), correspond to the set of possible determinants
of{−1, +1}-valued matrices. Understanding this set for
general n is an open problem and is considered more
difficult than establishing an upper bound on the maximum value of the determinant.
• For n = k, there is a one-to-one correspondence between global optima and distinct maximal-determinant
[−1, +1]-valued matrices.
Finally, we state the following lemma, which follows directly
from the proof of Lemma 1:
Lemma 2. There will always be a global optimum of (2)–(3)
on a vertex of a feasible region. If a Hadamard matrix exists,
then all global optima of (2)–(3) are strict and lie on vertices.
B. Behavior of Algorithm 2
In this subsection, we show that Algorithm 2 is guaranteed
to terminate at a vertex of the feasible reason. This result is
important because all solutions to the blind decoding problem
will lie on these vertices, as shown in the following claim.
Claim 1. Solutions to the blind decoding problem lie on
vertices on the feasible region, defined by (3).
Proof. This is a simple consequence of the fact that X ∈
{−1, +1}n×k . Any U which takes UY to {−1, +1}n×k will
satisfy exactly kn constraints from (3) with equality. Since
the constrained region is given by a polytope with 2kn faces,
kn of which are linearly independent, this corresponds with a
vertex of the feasible region.
Notice that because (2) is not convex, Claim 1 is not
immediately obvious, nor is it obvious that either gradient
descent or Algorithm 2 will terminate at a vertex. We show
that there is a small but non-zero chance that gradient descent
will not terminate at a vertex. This motivates the study of
Algorithm 2 over Algorithm 1. Concretely, our first result
regarding the behavior of Algorithm 2 is stated as follows:
Theorem 1. Algorithm 2 terminates at a vertex of the feasible
region of (2)–(3) with probability 1.
The full proof of this theorem is contained in Appendix C.
Here, we sketch the proof of this theorem which will also give
the reader intuition as to why the blind decoding problem can,

7

at reasonable dimensions, be practically solved by gradient
descent or other similar optimizations methods.
The first step in the proof of Theorem 1 is showing that all
optima lie on the problem boundary. This is formally proven
in Lemma 4. This lemma is a simple consequence of the
facts that the objective function consists of the composition
of a monotonically increasing function (the logarithm) and a
multilinear function (the determinant), and that the problem
boundary is convex. These facts imply that, given any point
within the feasible region that does not lie on the boundary, we
can always move away from the origin in a way that increases
the objective function.
We have already established in Lemma 2 that when a
Hadamard matrix exists, all optima are strict. Conversely,
at dimensions where Hadamard matrix do not exist, then
one can find non-strict optima. From Lemma 4, we know
that these non-strict optima must lie on the boundary of the
feasible region. In Lemma 5 and Corollary 1, we further
characterize these non-strict optima to show that if a non-strict
optima exists, then they must be restricted to a linear interval
contained on a face of the polytope which defines the feasible
region. We further show that all strict optima, regardless of the
existence of a Hadamard matrix must lie on vertices. We use
these fact together with Lemma 3 to guarantee that Algorithm
2 reaches a vertex.
In Lemma 6, we show how far gradient descent (or Algorithm 1) will proceed towards a vertex. Notice that the
constraints in (3) act on each row of U independently, and
U will be at a vertex of the feasible region when there are
exactly n constraints active on each row. In fact, we show in
Lemma 6 that when gradient descent terminates (meaning we
have reached an optima), each row of U will have at least
n − 1 active constraints per row.
When this occurs, U will be on an edge of the feasible
region; indeed, there is exactly one line on which U can move
while staying on the boundary of the feasible region and not
affecting the active constraints. We can further show that the
objective function must be constant along this line. Thus, for
each row with n−1 active constraints, we can simply choose a
direction at random and move in this direction until we reach a
vertex. We are thus guaranteed that Algorithm 2 will terminate
at the vertex of the feasible region.
C. Maximal Subset Property
We have established that Algorithm 2 always terminates on
a vertex of the feasible region. However, such a point may
either be a global or local optima to (2)–(3) and may not
correspond to a solution to the blind decoding problem. In
this light, we now study when vertices of the feasible region
correspond to solutions to the blind decoding problem and
understanding when, if ever, local optima of (2)–(3) exist. We
first derive a sufficient condition for the solutions of the blind
decoding problem to correspond to global optima of (2)–(3).
More precisely, we will study the following condition of the
set {x1 , . . . , xk }:
Definition 1. A matrix X ∈ [−1, +1]n×k , and corresponding
set cols(X) ⊆ [−1, +1]n , with k ≥ n has the maximal subset

property if there is a subset cols(V) ⊆ cols(X) of size n so
that if V ∈ Rn×n is the matrix with elements of cols(V) as
columns, then
| det V| =

max

W∈[−1,+1]n×n

| det W|.

(10)

That is, X has the maximal subset property if it contains
a subset of columns that, when viewed as a matrix, has
a determinant that is maximal among all [−1, +1]-valued
matrices (and hence also all {−1, +1}-valued matrices). With
this definition, we can now state a sufficient condition for
solutions to our problem to be global optima.
Lemma 3. If X has the maximal subset property, then, for
all ATMs T, all matrices in the form U = TA−1 are global
optima of (2)–(3).
Lemma 3 is proved in Appendix B. For small n, we can
compute the probability that a set of k samples has the
maximal subset property; this result is given in Appendix F. In
Section VI we show that the empirical success probability of
Algorithm 1 with k samples exactly matches the probability
distribution derived in Appendix F.
It is natural to ask whether the converse of Lemma 3 is true.
In fact, for M > 2, an explicit counterexample exists, found
through computer simulation, that shows that the maximal
subset property is not a necessary condition. This is important
because the probability of finding a maximal subset through
uniform sampling decreases rapidly as M and n grow. Indeed,
this agrees with our empirical observations, specifically Table I
found in Section VI, which show that the increase in k required
to maintain a constant success probability (assuming uniform
sampling) appears less than quadratic in M . Having established the maximum subset property as a sufficient condition,
we now continue our analysis of the geometry of our nonconvex optimization problem by considering specific values
of n.
D. The Cases n = 2 and n = 3
For n = 2 and n = 3, it can easily be checked that all
full-rank matrices in {−1, +1}n×n have the maximal subset
property. In other words, the set of possible values of the
determinant contains two possible absolute values, 0 and 2n−1 .
For n = 2, one can verify that ATMs are the only orthogonal
matrices that map elements of this set to other elements of
this set. Further, since a Hadamard matrix exists at n = 2,
all optima are strict and vertices of the feasible region. These
facts imply the following theorem.
Theorem 2. For n = 2, Algorithms 1 and 2 are correct (that
is, finds a solution to the blind decoding problem) if and only
if X has the maximal subset property.
For n = 3, the maximal subset property alone is not
sufficient to ensure that Algorithms 1 or 2 succeed. Indeed,
for any X ∈ {−1, +1}3×3 , there exists a matrix Q such that
QX ∈ [−1, +1]3×3 , det Q = ±1 and Q ∈
/ T . This implies the
existence of spurious optima whenever k = 3. However, these
spurious optima will not exist if k ≥ 4 and X contains at least
one additional distinct column beyond the three required for

8

the maximal subset property. By a distinct column, we mean
that the ith column of X is distinct if xi 6= ±xj for all j 6= i.
Notice that this also implies that all columns of X are pairwise linearly independent. Further, we note that Algorithm
1 is no longer guaranteed to be correct for n = 3 because
n = 3 contains no Hadamard matrix. We now formally state
a theorem, proven in Appendix D, regarding the performance
of Algorithm 2.
Theorem 3. When n = 3, Algorithm 2 is correct with
probability 1 if and only if k ≥ 4 and there exists a 3×4 matrix
V, such that cols(V) ⊆ cols(X), span(v1 , . . . , v4 ) = R3 , and
all vectors in V are pair-wise linearly independent.
We now turn our attention to quantifying the probability
that the conditions required by Theorems 2 and 3 hold. Let
r(n, k) denote the probability that a collection of k vectors in
Fn2 has rank n (and hence the rank in Rn must also be n),
then the probability of the solver succeeding, given k samples
chosen uniformly at random, is given by:
Pr(Success) = r(n, k).

(11)

An explicit formula for r(n, k) is derived in Appendix F.
Notice that for n = 2, equation (11) expresses the probability
that the set of global optima contains solutions to the blind
decoding problem. For n = 3, since we require the existence
of a fourth distinct vector, we find that the probability, for a
set of k samples chosen uniformly, that all global optima will
be solutions to be
Pr(Success) = r(n, k) · (1 − 2n−k ).

(12)

We note that, for n = 3, if a collection of samples contains
only the MSP and not an additional distinct column, then Algorithm 2 still has a non-zero probability of finding a solution
to the blind decoding problem as the set of global optima
still contains the set of all solutions. Thus the probability of
success of Algorithm 2, conditioned over a uniform selection
of samples, is bounded between (11) and (12). In Section VI
we compare these distributions to our empirical results.
E. The case n = 4.
At dimension n = 4, the problem geometry gets slightly
more complicated. The set of possible values of the determinants of {−1, +1}4×4 increases to {0, ±8, ±16}, which means
that not all non-singular vertices of (3) are global optima to
(2)–(3). However, we show that for n = 4, the only optima of
(2)–(3) are indeed global optima. Unfortunately, for n = k, not
all global optima are solutions to the blind decoding problem.
Nonetheless, we are able to show that for n = 4, Algorithms
1 and 2 both succeed (and solve the blind decoding problem)
with probability 1 under proper input conditions.
Before stating Theorem 4, which is proved in Appendix
E, we must also introduce equivalence classes of Hadamard
matrices. We say that two Hadamard matrices H1 and H2 are
equivalent if there exists and ATM T such that H1 = T · H2 .
This is an equivalence relation, and thus decomposes the set
of Hadamard matrices into equivalence classes. For n = 4,

there are exactly two equivalence classes, which we denote as
(1)
(2)
H4 and H4 , that are defined as follows:
 


1 1 1 1




 


1
1
−
−
(1)


H4 = T 
,
∀T
∈
T
,
(13)
1 − 1 −






1 − − 1
 


− 1 1 1






1 − 1 1
(2)
 , ∀T ∈ T ,
H4 = T 
(14)
1 1 − 1






1 1 1 −
where “−” denotes −1. Notice that all vectors in F42 appear
(1)
(2)
as column vectors in either H4 or H4 . We say that a vector
belongs to an equivalence class if it appears as a column vector
in that equivalence class. We now state our result for the case
n = 4, which is proven in Appendix E. Notice that because
a Hadamard matrix exists for n = 4, then by Lemma 2, the
only optima of (2)–(3) are strict and hence gradient descent
will always terminate at a vertex even without the modification
given in Algorithm 1.
Theorem 4. When n = 4, Algorithm 1 is correct with
probability 1 if and only if k ≥ 5 and cols(X) contains at
(i)
least four linearly independent vectors from H4 and a fifth
(j)
vector from H4 for i 6= j.
Algorithm 1 will be correct with probability 0.5 if cols(X)
has only four linearly independent vectors belonging to the
same equivalence class.
Theorem 4 implies that we will always require at least 5
samples in order to solve the blind decoding problem. Further,
assuming that the source symbols are chosen uniformly at random, this result allows us to quantify the success probability
of the blind decoding algorithm. This is done in Appendix E,
where we show that the success probability for n = 4 is given
by:
Pr(Success) = r(4, k) · r(3, k)4 · (1 − 2n−k ).
(15)
F. Larger n
In this subsection we discuss the performance of Algorithm
1 for larger values of n. In Figure 2 we use Algorithm 1 to
attempt to find maximal determinant matrices, as described
in Lemma 1. For 1 ≤ n ≤ 5, Algorithm 1 terminated at a
global maximum 100% of the time, supporting the claim that
there are no local maxima in these cases, as explicitly proven
for dimension 1,2,3, and 4. This also suggests that a similar
theoretical guarantee may exist for n = 5, but proving such a
result in the same manner as used for the case n = 4 would
be computationally expensive.
For dimensions n > 5, such an analysis seems extremely
difficult. Indeed, for even reasonably small values of n, the set
of possible determinants of {−1, +1}-valued matrices is not
well understood, and for very large values of n the maximal
value of the determinant is only known for special cases of n:
see, for example, [25].
We can however compare Figure 2 with results obtained in
Section VI (notably Figure 4). Despite the fact that the odds of
finding a global optima decreases when n grows with k = n,

1

1

0.9

0.9

0.8

0.8

0.7

0.7

Success Probability

Success Probability

9

0.6
0.5
0.4

0.6
0.5
0.4

0.3

0.3

0.2

0.2

0.1

0.1

0

0

2

4

6

8
n

10

12

14

0

16

Fig. 2. The probability that Algorithm 2 finds a maximal-determinant matrix
when used as described in Lemma 4, averaged over 1000 samples. For
dimension at most 5, all optima are global. Above this, we are not guaranteed
to find terminate at a maximal matrix. However, as k grows relative to n, the
probability increases again. See Figure 3.

0

Having established theoretical results regarding the correctness of our algorithm, we now turn our attention to empirical
results. The simulation results contained in this section are
entirely based on Algorithm 1 and demonstrate that Algorithm
2 is unnecessary in practice, at least for low dimensions. The
empirical performance of Algorithm 2 does not noticeably
improve over the performance of Algorithm 1. In order to
assess the performance of Algorithm 1, we constructed two
sets of experiments. In the first, we ran Algorithm 1 for
various values of n and M without channel noise in order
to empirically test the conditions under which the solver will
return the correct solution. In the second, we ran the algorithm
using realistic channel conditions and compared the results
to the Zero-Forcing and Maximum-Likelihood decoders, both
with perfect and imperfect CSI.

10

15

Fig. 3. Success probability of Algorithm 1 versus number of samples for
n = 2, 3, 4 and M = 2. Simulations were run over 200 trials. The predicted
results are the probability that X has the requisite subset of columns to ensure
correctness of Algorithm 1, as discussed in Section V and Appendix F.

1
0.9
0.8

Success Probability

VI. E MPIRICAL R ESULTS

5

Samples

the probability of success of Algorithm 1 empirically grows
toward 1 when k is sufficiently large. Intuitively, this happens
because adding additional constraints removes vertices from
the feasible region. This has the effect of removing both local
optima as well as global optima that do not correspond to
solutions to our problem. Based on the theory established in
this section and empirical results from Section VI, we make
the following conjecture about the behavior of Algorithms 1
and 2 for general values of n.
Conjecture 1. If k is slightly larger than n, and if X is
selected uniformly from the set of all n × k matrices that have
the maximal subset property, then with high probability, the
only optima in (2)–(3) are U = TA−1 , for all ATMs T.

n=2,Simulated
n=2,Predicted
n=3,Predicted Upper Bound
n=3,Simulated
n=3,Predicted Lower Bound
n=4,Simulated
n=4,Predicted

0.7
0.6
0.5
0.4
n=2
n=3
n=4
n=5
n=6
n=7
n=8

0.3
0.2
0.1
0

0

10

20

30

40

Samples
Fig. 4. Empirical success probability of Algorithm 1 for n = 2, . . . , 8 and
M = 2 with no AWGN. Simulations were run over 200 trials. Beginning at
n = 6, local optima exist when n = k and X contains the maximum subset
property. However, as k increases these local optima may become infeasible,
increasing the success probability of Algorithm 1.

10

TABLE I
S AMPLE S IZE R EQUIREMENTS

n
2
3
4
5
n
2
3
4
5

Algorithm 1
M=2
M=4
M=8
M=16
5
14
29
56
6
23
45
87
10
32
60
118
14
42
98
150
Algorithm presented in [10]
M=2
M=4
M=8
M=16
5
33
182
913
13
182
2,006
20,326
33
913
20,326
416,140
79
4,369
196,711
8,111,980

The table at the top shows the number of samples required for various values
of n and M to recover U in the correct form with 90% success rate using
Algorithm 1. The table at the bottom represents the number of samples needed
to ensure a 90% success rate using either the ILSP or the ILSE techniques
presented in [10].

Table I summarizes the number of samples required for
various values of n and M so that Algorithm 1 has a 90%
probability of returning an optimal solution to (2)–(3). For the
values of n presented, the success probability is almost entirely
conditioned upon the input value of X rather than randomness
in Algorithm 1; that is, running Algorithm 1 multiple times
on the same X will not improve success rates.
Figure 3 shows the expected success rate for n = 2, 3, 4
which is based on the theory in Section V and Appendix F. The
results in this plot are for the case M = 2 which corresponds
to Binary Phase Shift Keying (BPSK) in the absence of noise.
For n = 2, the theoretical success probability is the probability
that X has the maximal subset property. For n = 3 and
n = 4, success is only guaranteed if X has the maximal
subset property as well as at least one additional distinct vector.
For n = 3, the expected success rate of Algorithm 1 is not
known when X has the maximal subset property alone. The
probability that X has the maximal subset property is plotted
as a lower bound on performance in this case; the upper bound
given in Figure 3 expresses the probability that X has the
maximal subset property as well as one additional vector. For
n = 4, as shown in Section V, we know that Algorithm 1 will
succeed with probability 0.5 when X has the maximal subset
property alone; this is reflected in the theoretical prediction
for this case. We note that for n = 2, 3, and 4, the empirical
observations match the expected theoretical performance.
Figure 4 shows the empirical success probability of Algorithm 1 up to n = 8. This plot demonstrates two important
features regarding the performance of Algorithm 1 as n grows.
First, for n > 5, it is know that local optima may exist. Figure
2 from Section V gives the probability that when n = k and X
has the maximal subset property, Algorithm 1 will find a global
optima. However, we can see in Figure 4 that for large enough
values of k, the success probability of Algorithm 1 exceeds
this probability. This is because these additional samples cause
local optima to become infeasible, increasing the probability
Algorithm 1 will find a global optima. Additionally, these
results show that the required values of k appear to scale
favorably as n grows. We further note that n ≤ 8 captures

nearly all MIMO systems found in use today.
Figures 5 and 6 shows the symbol error rate performance
of the blind decoder compared to standard MIMO decoding
algorithms. Figure 5 gives an example with high SNR and high
modulation order, with the parameters n = 3, M = 32, c = 3,
while Figure 6 shows the case n = 4, M = 2, c = 3 at SNR
values typically found in modern cellular systems. Despite
having less side information, the performance of the blind
decoder (Algorithm 1) is only slightly worse than the ZF and
ML decoders with perfect CSI; there appears to be less than
3 dB loss associated with the blind decoder. The simulation
used a fading block length of 400 samples, and ran over a
total of 500 fading blocks per SNR. In high dimensions, large
numbers of constraints leads to numerical instability, requiring
the step size to be extremely small, and making the solver
slow to converge. Improving the runtime of our algorithm, for
example through an intelligent selection of a subset of received
samples, is a topic of future research.
Motivated by real-world usage, we compared blind decoding
(Algorithm 1) to the ZF and ML decoders with imperfect
CSI. If we assume that the channel is estimated through a set
of known pilot symbols that will be corrupted by Gaussian
noise, the error in the CSI will be i.i.d. Gaussian. This is a
realistic assumption in most wireless systems, and the model
we used in our simulations. In Figures 5 and 6, we also plot
the performance of Algorithm 1 against ZF and ML when the
variance of the error in the channel gain matrix is 1% of that
of the AWGN in the channel and for 10% estimation error. In
both cases, Algorithm 1 significantly outperforms the ZF and
ML decoders.
VII. C ONCLUSION
We have provided an algorithm to jointly estimate MIMO
channels and decode the underlying transmissions in block
fading channels. This algorithm performs gradient descent on a
non-convex optimization problem. Empirically, this algorithm
has a performance loss on the order of several decibels
versus schemes with perfect CSI, but its performance becomes
superior when CSI knowledge is imperfect. This algorithm
is practical in that it works well for block-fading channels
with realistic coherence times. In addition to the important
application of decoding in MIMO channels with missing or
imperfect CSI, our algorithm is potentially useful from the
point of view of an eavesdropper who does not know the pilot
symbols but is trying to recover x.
We present in-depth analysis of the geometry of this nonconvex optimization problem. Specifically we prove that for
M = 2, and small values of n, all optima are global and
give necessary and sufficient conditions for when these optima
correspond to solutions to the blind decoding. For general
values of n, we relate the problem to the Hadamard Maximal Determinant problem and give evidence that providing
matching theoretical guarantees for larger values of n is
likely difficult. However, our empirical results suggest that our
algorithm remains feasible for values of n commonly found
in modern MIMO systems.
This paper also motivates a suite of open theoretical problems related to the performance of our algorithm. For example,

11

0

10

Blind Decoding
Zero Forcing with Perfect CSI
ML SVD with Perfect CSI

Blind Decoding
Zero Forcing with Perfect CSI
ML SVD with Perfect CSI

10 -2

Bit Error Rate

Symbol Error Rate

10-1

10 -3

-2

10

10-3

10 -4
32

33

34

35

36

37

38

SNR (dB)

10-4

10 -1

6

8

10

12

14

16

18

20

16

18

20

SNR (dB)
100

10-1

10 -2
Bit Error Rate

Symbol Error Rate

Blind Decoding
Zero Forcing, 10% est. error
ML SVD, 10% est. error
Zero Forcing, 1% est. error
ML SVD, 1% est. error

10-2

10 -3

Blind

10-3

ML SVD, 1% est. error
ZF, 1% est. error
ML SVD, 10% est. error
ZF, 10% est. error

32

33

34

35

36

37

38

SNR (dB)
Fig. 5. Decoding performance for n = 3, M = 32, c = 3 compared to the
zero-forcing and maximum-likelihood decoder, implemented through parallel
channel decomposition. The top figure has no estimation error present, the
bottom figure has compares blind decoding to both ML and ZF decoding
with imperfect CS. These figures show that if the error in the CSI is even
one percent of the channel noise variance, then blind decoding outperforms
both these algorithms. The blind decoding algorithm appears to have at most
a 3dB loss over decoding with perfect CSI.

we provide no theoretical results that analytically explain the
performance in the presence of AWGN, and for M > 2. We
also leave open possible extensions to rectangular or complexvalued channels, as well as more efficient algorithms than
gradient descent that solve the blind decoding problem.
A PPENDIX A
P ROOF OF P ROPOSITION 1
In this appendix, we prove the result of Proposition 1 shows
that solutions to (2)–(3) are meaningful if and only if the
channel gain matrix is full rank.

10-4

6

8

10

12

14

SNR (dB)

Fig. 6. Decoding performance for n = 4, M = 2, c = 3. The decoding
performance is similar in comparison to standard MIMO algorithms as the
n = 3, M = 32 case shown in Figure 5.

Proposition 3. If the matrix Y is not full rank, then (2)–(3)
is unbounded above. Conversely, if Y is full rank and k ≥ n,
then (2)–(3) is bounded above and feasible.
Proof. If Y is not full rank, then there is some nonzero vector
v ∈ Rn s.t. vT Y = 0. Then the matrix



vT

 −1

 Y

UY = c1 · 
A + c2 · 

0
= c1 X + c1 A−1 e

(16)

satisfies (3), for some value of c1 , but the objective function

12

(2) grows without bound as c2 grows.
Conversely, if Y is full rank and k ≥ n, then the left
nullspace of Y is {0}. Thus, any non-zero row in U will
always affect (3) and the maximum kui k2 will be bounded
above for all i, implying that (2) is bounded above. Similarly,
for any Y, there will always be U that satisfies (3), for
example, consider U = 0.
A PPENDIX B
P ROOF OF L EMMA 3
Lemma 3. If X has the maximal subset property, then, for
all ATMs T, all matrices in the form U = TA−1 , are global
optima of (2)–(3).
Lemma 3 follows from the following claim.
Claim 2. Suppose that X has the maximal subset property.
Then for all matrices M such that kMxk∞ ≤ 1 for all x ∈ X,
we have | det M| ≤ 1.
Proof. Let x1 , . . . , xn be the set guaranteed by the maximal
subset property. Let V be the matrix whose columns are
x1 , . . . , xn , so | det V| is maximal. If | det M| > 1, then
| det MV| > | det V|. This would imply that MV cannot
be contained in [−1, +1]n×n .
Thus, if the matrix X has the maximal subset property, then
the optimal solution to (2)–(3) have | det UA| = 1, and hence
all U = TA−1 correspond to global optima. This completes
the proof of Lemma 3.
A PPENDIX C
P ROOF OF T HEOREM 1
Theorem 1. Algorithm 2 terminates at a vertex of the feasible
region with probability 1.
We begin the proof of Theorem 1 with a lemma that is
a simple consequence of the fact that the determinant is a
multilinear function.
Lemma 4. All optima of (2)–(3) lie on the boundary of the
feasible region.
Proof. Consider a feasible, full-rank U which is not on the
boundary of the feasible region, i.e. kUyi k∞ < 1 for all
i ∈ [1, . . . , k]. Suppose |u(j) yi | = c for some i, j and some
0 < c < 1. If we set
ũ(j) = (1 + )u(j)

(17)

for some 0 <  ≤ c, and form Ũ from the matrix U by
replacing row u(j) with ũ(j) , then, because the determinant is
linear in the rows of U, we have:
| det Ũ| = (1 + )| det U| > | det U|

(18)

and Ũ is still feasible.
In other words, if U is not on the problem boundary, the
multilinearity of the determinant function implies that we can
always move towards the problem boundary (and away from
the origin) in a way that increases the objective function.

We can also use the fact that the feasible region is formed
by an n-dimensional polytope to further categorize the optima
of our optimization problem, as stated in the following lemma.
Let P denote the polytope that describes the feasible region
given by (3), and let F denote a face of this polytope. Since
each row of the matrix U acts on the constraints in an
independent manner, we say that a row is “active” if there
are n linearly independent constraints active on this row. If all
rows of U are active then U is a vertex of P; further, if there
are i active rows, then U lies on a face of dimension at most
n(n − i).
Lemma 5. Suppose that U is in the interior of a face F.
Then there exists a v ∈ Rn , i ∈ [n], λ1 < λ2 ∈ R such that
the interval I defined as
I = {U + λei v| | λ ∈ [λ1 , λ2 ]}

(19)

satisfies I ⊆ F. Further, the points given by U + λj ei v| for
all j = 1, 2 lie on a face of lower dimension than F.
Proof. The polytope P is bounded by |hu(j) , y(i) i| ≤ 1 for
y(1) , . . . , y(k) and all rows u(j) of U. If U is not at a vertex,
then there exists a row u(j) that is not active. For this nonactive row u(j) , say that Ω = {y(i) | |hu(j) , y(i) i| = 1}. We
must have dim(Ω) < n. Thus, there exists a v ∈ Ω⊥ and a
y(i) ∈
/ cols(Y) such that hv, y(i) i 6= 0. This is true since if,
for all y(i) ∈ Y, hv, y(i) i = 0, then Y is not full rank. We
now require the following claim:
Claim 3. For small enough λ, U + λej v| ∈ F.
Proof. The quantity λej v| only affects constraints acting on
row j of U, and for all y(i) ∈ Ω, (U + λej v| ) · y(i) = Uy(i) .
Thus, no active constraints have been affected which implies
that we have not left the face F.
It remains to show that for appropriate values of λ1 and λ2 ,
the points given by U + λj ei v| , for all j = 1, 2, lie on a
lower dimensional face than F. Since there exists a y(i) such
that hv, y(i) i 6= 0, there must be exactly two values λ1 , λ2
such that huj + λi ej v| , y(j) i = ±1. Thus, for these bounding
values of λ, an additional constraint will be active, implying
that U + λj ei v| will be on a lower dimensional face than
F.
Having established Lemma 5, we now show the following
corollary which allows us to further characterize the optima
of (2)–(3).
Corollary 1. Non-strict optima (which by Lemma 4 must
lie on a face F) are restricted to an interval I as given in
(19). Further, the end points of this interval lie in a lower
dimensional face.
Proof. Suppose U is a non-strict optima in the interior of some
face. By Lemma 5 and the multilinearity of the determinant,
there must exist an interval I over which the objective function
is constant valued.
We also remark, informally, that Lemma 5 also implies that
all strict optima will in fact be vertices of the feasible region.
By Lemma 5 and Corollary 1, for any U that lies on the

13

interior of a face, U is not a strict optimum. Indeed, there
must either be a direction ei v| along which U may move
either to increase the value of the objective function or keep
the objective function constant. This result is not needed to
complete Theorem 1, but provides insight into the geometry
of the problem.
Having characterized the set of optima in (2)–(3), we now
turn our attention to characterizing the behavior of Algorithms
1 and 2. To do so, we will consider the gradient of the objective
function, which is given in [20] as
|
(20)
∇ log | det U| = U−1 .
We note that an alternative proof of Lemma 4 follows from
the fact that the gradient is non-zero as long as U is finite.
In order to understand how gradient descent will behave
on the boundary of the feasible region, we must consider
directional derivatives for directions that lie on the problem
boundary. Let ∆ ∈ Rn×n be a direction such that, for feasible
U, U + ∆ is also feasible. Gradient descent will terminate if,
for all ∆,
D
| E
U−1 , ∆
≤ 0,
(21)
F

where h·, ·iF is the
Frobenius inner product.
| Thus, (21) is equal
| |
to vec U−1
vec(∆) or tr( U−1 ∆).
We now show that (21) can only hold if each row has either
n−1 or n active, linearly independent constraints. This lemma,
as well as Corollary 1, motivate Algorithm 2 as it implies
that there may be corner cases where Algorithm 1 will fail,
but these corner cases can easily be handled by forcing the
algorithm to terminate at the nearest vertex.
Lemma 6. If any row of U has fewer then n − 1 active
constraints, then there exists a non-zero matrix ∆ such that
U + ∆ satisfies (3) and log | det U + ∆| > log | det U|.
Proof. Consider the ith row of U, denoted u(i) , and let δ (i)
be the corresponding elements of ∆. The corresponding row
of the gradient matrix is given by:
(∇U)

(i)

=

1
c(i) ,
det U

(22)

where c(i) is the ith row of the cofactor matrix of U. Since
U must be full rank, c(i) must be non-zero for all i. Thus, for
any i, the only way in which we could have
1 D (i) (i) E
c ,δ
=0
(23)
det U
F
is if the only feasible values of δ (i) (i.e. those that do not move
U outside the feasible region) are orthogonal to c(i) .
If fewer than n − 1 linearly independent constraints are
active on the ith row, then there always is a subspace of at
least dimension two from which we can select δ (i) . Precisely,
suppose that the constraints given by y1 , . . . , yn−2 are active.
The subspace spanned by these vectors must always have a
null space of at least dimension two; if δ (i) is contained in
this nullspace then U + ∆ will be feasible. As long as this
nullspace has dimension at least two, for all i, there exists a
δ (i) such that U + ∆ satisfies (3) and that has hc(i) , δ (i) i =
6 0.

Thus, gradient descent will always proceed as long as fewer
than n − 1 constraints are active on each row.
In other words, by Lemma 6, if gradient descent terminates
and we are not at a vertex, there must be at least one row
with exactly n − 1 active, linearly independent constraints.
In this case, we may move along the interval I guaranteed
by Corollary 1 until we reach a lower dimensional face.
This lower dimensional face will either be a vertex, in which
case we have reached a strict optima and the algorithm will
terminate, or there will exist a positive gradient and we can
resume gradient descent. This completes Theorem 1.
A PPENDIX D
P ROOF OF T HEOREM 3
Theorem 3. When n = 3, Algorithm 2 is correct with
probability 1 if and only if k ≥ 4 and there exists a 3×4 matrix
V, such that cols(V) ⊆ cols(X), span(v1 , . . . , v4 ) = R3 , and
all vectors in V are pair-wise linearly independent.
We know that if X has the maximal subset property, then
Algorithm 2 will always terminate at a global maximum of
(2)–(3) and that the set of global optima contains all solutions
in the form TX for all T ∈ T . However, for n = 3,
the maximal subset property alone does not ensure that all
global optima will be solutions to the blind decoding problem.
Spurious optima must have the form QX ∈ [−1, +1]n×k ,
where det Q = ±1 and Q ∈
/ T . Algorithm 2 will only be
correct with probability 1 if there are no spurious optima.
We now show that, for n = 3, if X has four distinct
columns (distinct meaning pair-wise linearly independent),
QX ∈ [−1, +1]n×k and det Q = ±1 implies that Q ∈ T .
This further implies that all global optima are solutions to the
blind decoding problem. Consider the following choice of X:


1 1 −1 −1
(24)
X = 1 −1 1 −1 .
1 1
1
1
The following lemma shows that this choice of X further
restricts Q to be orthogonal.
Lemma 7. Suppose Q has det Q = ±1, and, for X given by
(24), if QX ∈ [−1, +1]3×3 , then Q ∈ O(3).
Proof. We know that, by Theorem 1, Algorithm 2 must terminate at a vertex. Thus, we must have QX ∈ {−1, +1}n×k ,
which further implies that, for all i, kQxi k2 = kxi k2 . We
now consider the set of linear operators with determinant ±1
whose action preserves the norms of each vector xi .
Define the operator Q̃ = ΣV| , where Σ denotes the
diagonal matrix containing the singular values of Q and V
denotes the right singular vectors of Q. Since Q = UQ̃, for
some U ∈ O(3), there must exist a Q̃ such that Q̃xi = ±xi
for all i; otherwise, kQxi k2 6= kxi k2 for some i.
We can consider√the action of any Q̃ on the surface of
a sphere of radius 3. This sphere, S, contains the vectors
that comprise the columns of X. Under the action of any
linear operator with determinant ±1, S will be mapped to an
ellipsoid, E, such that vol(E) = vol(S). Further, we know that

14

E, given by Q̃, must contain the points xi for all i. Lemma 7
is now completed by Claim 4, which shows that this is only
possible if E = S, implying that Q ∈ O(3).
Claim 4. The
√ only ellipsoid that is centered on the origin, has
volume 4π 3, and contains the points given by cols(X) is a
sphere.
Proof. Consider an arbitrary ellipsoid, E, centered about the
origin. For some A  0, this can be described by the following
equation





x

y

 a
z d
2
f
2

d
2

b
e
2

v| Av = 1,

f  
x
2
e 
y = 1.
2
z
c

a matrix Q with unit determinant such that QX ∈ [−1, +1]3×3
and Q ∈
/ T.
If X does not have four distinct columns then this will
always be the case. Consider the case where k > 3 and X has
the maximal subset property but no four columns of X are
distinct. Let the matrix V be formed from any subset of three
columns of X such that V has the maximal subset property.
Then we must have that for all i, there exists a j such that
xi = ±vj . For any Qvj ∈ [−1, +1]n , we also must have
−Qvj = Qxi ∈ [−1, +1]n . Thus, whenever X does not
contain any columns that are distinct from the columns of
V, then X will also have the same set of optima as V. This
completes Theorem 3.

(25)

We require the ellipsoid to contain the points (±1, ±1, 1). By
substituting these points into (25), it is seen that we must have
d = e = f = 0 and a + b + c = 1. Thus, A must be diagonal.
The eigenvalues of A are the inverse squares of the length
of the semi-axes of the ellipsoid. This implies√that the volume
4
of the ellipsoid is given by vol(E)
√ = 3 π/ abc. The only
solution that gives vol(E) = 4π 3 with a + b + c = 1 is
a = b = c = 31 , implying that the required ellipsoid in fact a
sphere.
Having established that (24) implies that Q ∈ O(3), we
can further show that the only feasible elements of O(3) are
in fact the ATMs.
Proposition 2. Suppose Q has Q ∈ O(3), and QX ∈
[−1, +1]3×4 , then Q ∈ T .
Proof. Notice that the vectors cols(X) form a face of the
unit cube. Since QX ∈ [−1, +1]3×4 and Q ∈ O(3), then
cols(QX) must also form the face of a unit cube. This is
because Q is orthogonal and must preserve norms and planes.
This fact restricts Q to the symmetries of the cube. There are
48 symmetries of the cube, which correspond to the set of 48
ATMs.
Finally notice that for all D = diag(±1, . . . , ±1), QX ∈
[−1, +1]n×k implies that QXD ∈ [−1, +1]n×k . Similarly, for
all permutation matrices P, QXP is feasible if and only if
QX is feasible. For n = 3, all possible ±1-valued matrices
that contain four distinct columns can be expressed as XPD.
This implies that if QX ∈ [−1, +1]3×4 , for any possible X
with four distinct columns, then Q ∈ T . Hence, any choice of
X with four distinct columns is sufficient to ensure that there
are no spurious optima.
We now turn our attention to showing the converse: that
requiring X to have four distinct columns (that is, pairwise
linearly independent) is in fact necessary for Algorithm 2
to be correct with probability 1. First, if n = k = 3, then
for any choice of X such that X has the maximal subset
property, spurious optima will exist. For n = 3, there is a
small collection of three vectors, up to the ATMs, that have
the maximal subset property, and so one may check that this is
always true. Therefore, when n = k = 3, there will always be

A PPENDIX E
P ROOF OF T HEOREM 4
In this appendix we prove Theorem 4, which gives necessary
and sufficient conditions so that Algorithms 1 and 2 return
correct solutions to the blind decoding problem when n = 4.
Notice that because a Hadamard matrix exists at n = 4, we
know by Lemma 2 the only optima are strict and are vertices
of the feasible region. Thus Algorithm 2 is not needed in this
case. Before considering the specific case of n = 4, we prove
the following more general statement for values of n such that
a Hadamard matrix exists. This result will be used in the proof
of Theorem 4. When a Hadamard matrix exists, we can further
characterize the solutions to (2)–(3) in the noiseless case as
follows.
Lemma 8. If n is such that Hadamard matrix exists, and X
has the maximal subset property, then the only global optima
to (2)–(3) on input Y = AX are of the form U = QA−1 ,
where Q ∈ O(n).
The following claim is helpful in proving this lemma:
Claim 5. For X ∈ Rn×n is an orthogonal matrix and some
M ∈ Rn×n with | det M| = 1, if kMxi k2 ≤ kxi k2 for all i,
then M must be orthogonal.
Proof. Let x1 , . . . , xn be the orthonormal basis obtained by
the columns of X.

tr MT M = MT M

2
F

=

n
X

|λi |2

(26)

i=1
n
X

xTi MT Mxi ≤

i=1

=
≤

n
X
i=1
n
X
i=1
n
X

|xTi MT Mxi |

(27)

|Mxi |2

(28)

|xi |2

(29)

i=1

=n

(30)

However, because | det M| = 1, this implies:
det MT M =

n
Y
i=1

λ2i = 1 =

n
X
i=1

|λi |2 ,

(31)

15

and by the inequality of arithmetic and geometric means, this
implies λ2i = 1 for all i. Since M is real valued, this implies
M is orthogonal.
By Lemma 2, we know that Q must have determinant
one. Let V be the matrix guaranteed by the maximal subset
property. V must be Hadamard. The matrix UAV, will
also have the maximum value of the determinant over all
[−1, +1]n×n matrices, and thus must also be Hadamard. Since
all points in V and UAV have `2 -norm 2n/2 , by Claim 5,
UA must be orthogonal. This completes the proof of Lemma
8.
At this point, one might be tempted to conjecture that, in
fact, the maximal subset property is on its own sufficient; that
is that the orthogonal matrix Q in Lemma 8 can be replaced
by an ATM T. However, this is not the case as we will show
in the proof of Theorem 4, given below.
Theorem 4. When n = 4, Algorithm 1 is correct with
probability 1 if and only if k ≥ 5 and cols(X) contains at
(i)
least four linearly independent vectors from H4 and a fifth
(j)
vector from H4 for any i 6= j.
Algorithm 1 will be correct with probability 0.5 if cols(X)
has only four linearly independent vectors belonging to the
same equivalence class.
We prove Theorem 4 in two parts. First, in Lemma 9,
we show that when n = k and X has the maximal subset
property, Algorithm 1 will return the correct solution to the
blind decoding problem with probability 0.5, and that with
the addition of an extra vector from a separate equivalence
class, all global optima correspond to solutions to the blind
decoding problem. In Lemma 9 we in fact prove a slightly
more general statement and give the probability of that all
global optima correspond to solutions of the blind decoding
problem given the input to Algorithm 1 is chosen uniformly
at random. Second, in Lemma 10, we show that for all values
of k, all optima are indeed global despite the fact that there
are suboptimal vertices.
Lemma 9. For n = 4, for a collection of k samples chosen
uniformly at random, the probability that all global optima
will correspond to solutions of the blind decoding problem is
given by
Pr(Success) = r(4, k) · r(3, k)4 · (1 − 2n−k ).

(32)

Proof. One can verify that for n = 4, for a matrix to have the
maximal subset property (and hence be a Hadamard matrix),
then not only must the matrix be full rank, but all matrices
obtained by choosing a subset of three rows must also be
full rank. The probability that a random set of k vectors of
dimension 4 is a Hadamard matrix given by:
Pr(Success) = r(4, k) · r(3, k)4 .

(33)

It can be seen that there is an orthogonal matrix, S, that is not
(1)
(2)
an ATM, such that for all G ∈ H4 , and H ∈ H4 , G = SH.
To find an example of such a matrix, for any choice of G and
H, compute S = G−1 H. This implies that, exactly half of the
global optima are solutions to (2)–(3). This is consistent with

the observation that if X has a maximal subset, then Algorithm
1 succeeds 50% of the time for n = 4, k = 4.
Notice that for this same G, H, and S given above, SG ∈
/
{−1, +1}4 and similarly S−1 H ∈
/ {−1, +1}4 , for all G and
H. Notice further that all vectors in {−1, +1}4 appear in either
(1)
(2)
H4 or H4 , and that the product of S times any vector in
(1)
(2)
H4 is not in {−1, +1}4 . Similarly, any S−1 times any H4
4
is not in {−1, +1} .
Now consider a collection of k > n vectors that contains
(i)
4 independent elements of H4 , for some i. If all vectors
in this collection belong to the same equivalence class, then
matrices containing a factor of S will be the optima of (2)–(3).
Otherwise, all such matrices will lie outside of the feasible
region and all global optima will correspond to solutions.
For this reason, adding constraints removes vertices from
the feasible region, thus increasing the success probability of
Algorithm 2.
Given the above argument, we have a probability of 1−2n−k
that the only global optima will be solutions, conditioned on
the fact that the matrix has the maximal subset property. Since
equation (33) gives the probability of the maximum subset
holding, we can express the probability that, given k random
samples, all global optima are solutions to (2)–(3) as:
Pr(Success) = r(4, k) · r(3, k)4 · (1 − 2n−k ).

(34)

In order to arrive at our desired result for n = 4, we still
need to show that no vertices that correspond to matrices with
determinant of ±8 are local optima of (2)–(3). This is proven
below and completes Theorem 4.
Lemma 10. For n = 4, all optima of (2)–(3) are global.
Proof. Optima of (2)–(3) can only lie on vertices of the
problem boundary — that is optima can only correspond to
non-singular {±1}-valued matrices by Lemma 2. We need to
show that no matrices with determinant ±8 are local optima.
We begin with two facts which have been verified through
computer simulation.
Create a graph with a node for each matrix in {−1, 1}4×4
and edges between each pair of nodes that have Hamming
distance of one. Remove from this graph all nodes which
correspond two determinant zero, leaving only nodes with
determinant ±8 and ±16. Since the determinant is a linear
function of the columns of a matrix, then the value of det A
changes linearly along each edge of this graph. Studying the
geometry of this graph will give us insight into paths that
Algorithm 2 may travel in arriving to an optima.
The first observation is that the graph is partitioned into
two components. This can be verified, for example, either
by inspecting the least eigenvalues of the Laplacian of the
adjacency matrix of the graph or performing a breadth-first
search. We find that one component of this graph corresponds
to {±1}-valued matrix that have positive determinants, and the
other to all all matrices with negative determinants. This means
that one can traverse either component of these graphs without
the objective function changing sign. This further implies that,
over each edge of the graph, the objective function is either

16



|
D = ṽ1
|



|
ṽ1
|

|
v2
|

|
v3
|

|
ṽ2
|





|
v4  = B
|

|
C = v1
|



|
A = v1
|

|
v2
|

|
v3
|

single n − 1 dimensional subspace is (1/2)k , by union bound,
we have the following probability:


|
v4 
|

|
v3
|

|
ṽ2
|

|
v3
|



|
v4 
|



|
v4 
|

Fig. 7. The matrix A with determinant 8 is Hamming distance 2 away from
the matrix D with determinant 16. A is Hamming distance 1 away from both
B and C which also have determinant 8. The objective function is constant
on the lines AB and AB but monotonically increasing on the line AD.

constant (and equal to log 8 along each edge), or changes
logrithmically from log 8 to log 16.
It can further be verified that the maximum Hamming distance between any matrix of determinant ±8 and determinant
±16 is 2. Those that have Hamming distance 1 are clearly
not local optima. Thus we turn our attention to the remaining
determinate ±8 matrices that have Hamming distance 2. Each
of matrices is connected to at least two determinant ±8
matrices that are distance 1 away from a ±16 matrix. This
is depicted in Figure 7: matrix A is distance 2 from optimal
matrix D and adjacent to suboptimal matrices B and C.
From Corollary 1, we know that the objective function can
only be constant on an affine subspace. It is constant along the
lines AB and AC, but not on the line between BD and CD.
This implies that the objective function cannot be constant on
the line AD. Further, we know that the determinants of A
and D have the same sign and that there cannot be critical
points on this line. Thus the objective function along this line
is monotonically increasing, implying that no determinant ±8
matrix is a local optimum.

A PPENDIX F
D ISTRIBUTION OF THE R ANK OF A C OLLECTION OF
R ANDOM V ECTORS
In this section, we consider the distribution of the rank of
a collection of vectors drawn uniformly from Fnq . Because the
rank of a collection of vectors in Fnq is less than or equal to its
rank in Rn , this will allow us to obtain an exact expression for
r(n, k), which is the probability that a set of binary vectors is
full rank over Rn . We begin by stating a simple lower bound
which shows that the probability of a collection of vectors
not being full rank decays exponentially fast as the number of
vectors grow. In this section we refer to k as the size of the
collection of vectors.
Noting that the number of subspaces of dimension n − 1
is 2n , and that the probability that all k vectors live in any

Pr(not full rank in Rn ) ≤ Pr(not full rank in Fn2 )
 k
1
n
= 2n−k
≤2
2

(35)
(36)

We now compute the exact distribution of the dimension of
the subspace spanned by a random subset of a vector space
over a finite field. From this distribution, we can compute an
exact expression for r(n, k). The computation makes use of
the Möbius inversion formula, a standard tool in combinatorics
and number theory that provides a natural way to count
elements of partially ordered sets using an overcountingundercounting procedure. For a full treatment on Möbius
functions and their applications see [26].
In [26], the authors apply Möbius inversion to counting
vector subspaces. If U and V are subspaces of Fnq , then
U ≤ V iff U is a subspace of V. This relation forms a
partial ordering for all subspaces of Fnq .
We are interesting in counting the number of collections
of vectors which span a given subspace. Let N= (X) be the
number of k-tuples (x1 , . . . , xk ) that span the subspace X,
and let N≤ (X) be the number of k-tuples that span either X
or a subspace of X. Clearly,
X
N≤ (X) =
N= (U)
(37)
U:U≤X

Note that the function N≤ (U) is easily computable as:
N≤ (U) = q (dim U)k .

(38)

The Möbius inversion formula gives us a way to compute
N= (U) through N≤ (U), namely:
X
N= (X) =
µ(U, X)N≤ (U),
(39)
U:U≤X

where µ is Möbius function, which is the integer-valued
function on ordered pairs of subspaces defined implicitly by:
(
X
1, if U = W
µ(U, X) =
(40)
0, if U 6= W.
X:U≤XW
µ may be computed recursively by the following formula:


U=W
1, P
µ(U, X) = − X:U≤X≤W µ(U, W), U < W
(41)


0, otherwise
In [26], the authors show that µ(U, X) depends only on the
difference between dim X and dim U. Letting i = dim X −
dim U, they further show that:
i

µ(U, X) = µi = (−1)i q (2) .

(42)

With these preliminaries, we now have everything we need to
prove the following theorem:

17

Theorem 5. Let the set of vectors x1 , . . . , xk be chosen
uniformly at random from Fnq , and let W denote the subspace spanned by these vectors. Then the probability that
dim W = m is:
  X
 
m
i
n
m
Pr(dim W = m) = q −nk
(−1)i q (2) q (m−i)k
.
m q i=0
i q
(43)
Proof. Note that there are q nk total possible k-tuples of
(x1 , . . . , xk ). This implies that
X
N= (X)
.
(44)
Pr(dim X = m) =
q nk
n
X≤Fq :dim X=m

We now compute N= (X) through the use of Möbius inversion,
using the expressions for N= (X), N≤ (X) and µi we derived
above, we have:
X
N= (X)
(45)
Pr(dim W = m) =
q nk
n
X≤Fq :dim X=m

=

=

1
q nk
1
q nk

X

X

µdim X−dim U N≤ (U)

(46)

X≤Fn
q :dim X=m U:U≤X

X

m
X

X

i

(−1)i q (2) q (m−i)k

X≤Fn
q :dim X=m i=0 U≤X,dim U=m−i

(47)
 
  X
m
i
m
n
= q −nk
(−1)i q (2) q (m−i)k
i q
m q i=0
where (47) and (48) follow by noting that
number of m-dimensional subspaces of Fnq .

(48)
n
m q

counts the

From this theorem, an expression for r(n, k) readily follows
by substituting m = n and q = 2:
 
n
X
i
n
.
(49)
r(n, k) = 2−nk
(−1)i 2(2) 2(n−i)k
i 2
i=0
ACKNOWLEDGEMENTS
The authors would like to thank Yonathan Morin for insightful conversation on MIMO decoding and channel estimation,
and for his comments on a preliminary version of this work,
Mainak Chowdhury for discussion on non-coherent MIMO
channels and optimization, Milind Rao for discussion on
optimization, blind-source separation and statistical learning
techniques, Ronny Hadani for his comments on the use of our
algorithm in complex-valued channels, and Jonathan Perlstein
for providing a counterexample for the n = 3, k = 3 case, and
for his comments on a preliminary version of this work.

R EFERENCES
[1] 3GPP, “TS 6.10.1.2 mapping to resource elements,” ETSI Tech. Rep.,
2010.
[2] R. Prasad, C. R. Murthy, and B. D. Rao, “Joint approximately sparse
channel estimation and data detection in OFDM systems using sparse
bayesian learning,” IEEE Trans. Signal Process., vol. 62, no. 14,
pp. 3591–3603, 2014.
[3] V. Tarokh, H. Jafarkhani, and A. R. Calderbank, “Space-time block
codes from orthogonal designs,” IEEE Trans. Inf. Theory, vol. 45, no. 5,
pp. 1456–1467, 1999.
[4] M. Chowdhury, A. Manolakos, and A. Goldsmith, “Scaling laws for
noncoherent energy-based communications in the SIMO MAC,” IEEE
Trans. Inf. Theory, vol. 62, no. 4, pp. 1980–1992, 2016.
[5] E. Jorswieck, S. Tomasin, and A. Sezgin, “Broadcasting into the uncertainty: Authentication and confidentiality by physical-layer processing,”
Proceedings of the IEEE, vol. 103, no. 10, pp. 1702–1724, 2015.
[6] S. Tomasin, “Analysis of channel-based user authentication by key-less
and key-based approaches,” CoRR, vol. abs/1705.03430, 2017.
[7] M. Grötschel, L. Lovász, and A. Schrijver, Geometric Algorithms and
Combinatorial Optimization. Springer, 1988.
[8] 3GPP, “TS 36.213 evolved universal terrestrial radio access (E-UTRA);
physical layer procedures,” ETSI Tech. Rep., 2010.
[9] IEEE Computer. Society, “Part 11: Wireless LAN medium access control
(MAC) and physical layer (PHY) specifications,” Std 802.11ac-2013,
2013.
[10] S. Talwar, M. Viberg, and A. Paulraj, “Blind separation of synchronous
co-channel digital signals using an antenna array. I. algorithms,” IEEE
Trans. Signal Process., vol. 44, no. 5, pp. 1184–1197, 1996.
[11] L. K. Hansen and G. Xu, “A hyperplane-based algorithm for the
digital co-channel communications problem,” IEEE Transactions on
information Theory, vol. 43, no. 5, pp. 1536–1548, 1997.
[12] P. Q. Nguyen and O. Regev, “Learning a parallelepiped: Cryptanalysis
of GGH and NTRU signatures,” in Annual International Conference on
the Theory and Applications of Cryptographic Techniques, pp. 271–288,
Springer, 2006.
[13] A. Hyvärinen and E. Oja, “Independent component analysis: algorithms
and applications,” Neural networks, vol. 13, no. 4, pp. 411–430, 2000.
[14] S. Ling and T. Strohmer, “Blind deconvolution meets blind demixing:
Algorithms and performance bounds,” arXiv:1512.07730, 2015.
[15] R. Johnson, P. Schniter, T. J. Endres, J. D. Behm, D. R. Brown, and
R. A. Casas, “Blind equalization using the constant modulus criterion:
A review,” Proceedings of the IEEE, vol. 86, no. 10, pp. 1927–1950,
1998.
[16] A. Benveniste and M. Goursat, “Blind equalizers,” IEEE Transactions
on communications, vol. 32, no. 8, pp. 871–883, 1984.
[17] S. M. Alamouti, “A simple transmit diversity technique for wireless
communications,” IEEE J. Sel. Areas Commun., vol. 16, no. 8, pp. 1451–
1458, 1998.
[18] B. Silverman and D. Titterington, “Minimum covering ellipses,” SIAM
Journal on Scientific and Statistical Computing, vol. 1, no. 4, pp. 401–
409, 1980.
[19] S. Boyd and L. Vandenberghe, Convex optimization. Cambridge university press, 2004.
[20] K. B. Petersen et al., “The matrix cookbook,” Sep. 2007.
[21] P. Diaconis and M. Shahshahani, “The subgroup algorithm for generating
uniform random variables,” Prob. In Eng. And Info. Sci, vol. 1, pp. 15–
32, 1987.
[22] J. Hadamard, “Résolution d’une question relative aux déterminants,”
Bull. Sci. Math., vol. 17, pp. 30–31, 1893.
[23] F. Macwilliams and N. Sloane, The Theory of Error-correcting Codes.
North-Holland, 2006.
[24] E. Tressler, A survey of the Hadamard conjecture. PhD thesis, Virginia
Polytechnic Institute and State University, 2004.
[25] R. P. Brent and J. H. Osborn, “On minors of maximal determinant
matrices,” Journal of Integer Sequences, vol. 16, no. 2, p. 3, 2013.
[26] E. Bender and J. Goldman, “On the appliations of Möbius inversion in
combinatorial analysis,” Am. Math Monthly, no. 82, pp. 789–803, 1975.

