Determining the feasibility conditions for vector space interference alignment in the K-user MIMO interference channel with constant channel coefficients has attracted much recent attention yet remains unsolved. The main result of this paper is restricted to the symmetric square case where all transmitters and receivers have N antennas, and each user desires d transmit dimensions. We prove that alignment is possible if and only if the number of antennas satisfies N>= d(K+1) 2. We also show a necessary condition for feasibility of alignment with arbitrary system parameters. An algebraic geometry approach is central to the results.
The main theoretical work to precede the present paper is by @cite_14 . Considering the case of a single transmit dimension, @math , they apply Bernstein's Theorem, which requires that each coefficient in a system of polynomial equations is chosen generically. They note that Bernstein's Theorem no longer applies in the case @math , as the equations describing the problem become coupled and coefficients are repeated. Our approach bypasses the difficulties posed by coupled equations, and thus, unlike @cite_14 our results do not have the restriction that @math .
@cite_14
2537174396 2591592591 2098102734 2168095411
This paper considers recovering @math -dimensional vectors @math , and @math from their circular convolutions @math . The vector @math is assumed to be @math -sparse in a known basis that is spread out in the Fourier domain, and each input @math is a member of a known @math -dimensional random subspace. We prove that whenever @math , the problem can be solved effectively by using only the nuclear-norm minimization as the convex relaxation, as long as the inputs are sufficiently diverse and obey @math . By “diverse inputs,” we mean that the @math ’s belong to different, generic subspaces. To the best of our knowledge, this is the first theoretical result on blind deconvolution where the subspace to which @math belongs is not fixed but needs to be determined. We discuss the result in the context of multipath channel estimation in wireless communications. Both the fading coefficients and the delays in the channel impulse response @math are unknown. The encoder codes the @math -dimensional message vectors randomly and then transmits coded messages @math ’s over a fixed channel one after the other. The decoder then discovers all of the messages and the channel response when the number of samples taken for each received message are roughly greater than @math , and the number of messages is roughly at least @math . This paper considers the problem of designing maximum distance separable (MDS) codes over small fields with constraints on the support of their generator matrices. For any given @math binary matrix @math , the GM-MDS conjecture, proposed by , states that if @math satisfies the so-called MDS condition, then for any field @math of size @math , there exists an @math MDS code whose generator matrix @math , with entries in @math , fits the matrix @math (i.e., @math is the support matrix of @math ). Despite all the attempts by the coding theory community, this conjecture remains still open in general. It was shown, independently by and , that the GM-MDS conjecture holds if the following conjecture, referred to as the TM-MDS conjecture, holds: if @math satisfies the MDS condition, then the determinant of a transform matrix @math , such that @math fits @math , is not identically zero, where @math is a Vandermonde matrix with distinct parameters. In this work, we first reformulate the TM-MDS conjecture in terms of the Wronskian determinant, and then present an algebraic-combinatorial approach based on polynomial-degree reduction for proving this conjecture. Our proof technique's strength is based primarily on reducing inherent combinatorics in the proof. We demonstrate the strength of our technique by proving the TM-MDS conjecture for the cases where the number of rows ( @math ) of @math is upper bounded by @math . For this class of special cases of @math where the only additional constraint is on @math , only cases with @math were previously proven theoretically, and the previously used proof techniques are not applicable to cases with @math . The paper introduces the sweeping preconditioner, which is highly efficient for iterative solutions of the variable-coefficient Helmholtz equation including very-high-frequency problems. The first central idea of this novel approach is to construct an approximate factorization of the discretized Helmholtz equation by sweeping the domain layer by layer, starting from an absorbing layer or boundary condition. Given this specific order of factorization, the second central idea is to represent the intermediate matrices in the hierarchical matrix framework. In two dimensions, both the construction and the application of the preconditioners are of linear complexity. The generalized minimal residual method (GMRES) solver with the resulting preconditioner converges in an amazingly small number of iterations, which is essentially independent of the number of unknowns. This approach is also extended to the three-dimensional case with some success. Numerical results are provided in both two and three dimensions to demonstrate the efficiency of this new approach. We explore the feasibility of interference alignment in signal vector space-based only on beamforming-for K-user MIMO interference channels. Our main contribution is to relate the feasibility issue to the problem of determining the solvability of a multivariate polynomial system which is considered extensively in algebraic geometry. It is well known, e.g., from Bezout's theorem, that generic polynomial systems are solvable if and only if the number of equations does not exceed the number of variables. Following this intuition, we classify signal space interference alignment problems as either proper or improper based on the number of equations and variables. Rigorous connections between feasible and proper systems are made through Bernshtein's theorem for the case where each transmitter uses only one beamforming vector. The multibeam case introduces dependencies among the coefficients of a polynomial system so that the system is no longer generic in the sense required by both theorems. In this case, we show that the connection between feasible and proper systems can be further strengthened (since the equivalency between feasible and proper systems does not always hold) by including standard information theoretic outer bounds in the feasibility analysis.