PaperlayerView exact revision on arXiv

Source-linked AI summary

On Feasibility of Interference Alignment in MIMO Interference Networks

Cenk M. Yetis, Tiangao Gou, Syed A. Jafar, Ahmet H. Kayran

arXiv:0911.4507v1cs.IT

TL;DR

The paper asks when beamforming-based interference alignment is feasible in K-user MIMO interference channels. It maps alignment to multivariate polynomial solvability and classifies systems by equations and variables. Single-beam cases support this connection rigorously, while multi-beam cases require coefficient-dependency awareness and information-theoretic outer bounds.

  • Problem

    The central question is how to determine alignment feasibility analytically, especially when multi-beam polynomial systems are non-generic.

  • Method

    The paper models signal-space alignment as solvability of a multivariate polynomial system and uses properness, Bernshtein-based reasoning, numerical tests, closed-form solutions, and outer bounds.

  • Results

    For single-beam cases, feasibility is connected to solvability through equation-variable counting; for multi-beam cases, properness is strengthened with general and cooperative outer bounds.

  • Takeaways & Limitations

    Properness provides an analytical feasibility framework for single-beam alignment, while multi-beam analysis must account for polynomial coefficient dependencies and outer bounds.

  • Takeaways & Limitations

    Multi-beam polynomial systems remain insufficiently characterized by current algebraic-geometry results because their coefficients can be dependent.

Abstract

from arXiv · show

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, 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 multi-beam 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.

I. INTRODUCTION

The paper studies whether beamforming-based signal-space interference alignment is feasible in symmetric and asymmetric K-user MIMO networks. It frames feasibility as solvability of a multivariate polynomial system and motivates analytical tests beyond numerical evidence.

  • Motivation: Interference alignment consolidates multiple interfering signals into a small subspace, preserving interference-free dimensions for desired signals.
  • Motivation: Signal-space alignment uses spatial dimensions and linear beamforming, offering analytical tractability and relevance to finite-SNR settings.
  • System classes: Symmetric systems use common transmitter antennas, receiver antennas, and DoF demands, whereas asymmetric systems allow these quantities to vary by user.
  • Feasibility question: The paper asks whether feasibility can be determined analytically for systems such as (2 × 2, 1)3 and (5 × 5, 2)4 without closed-form solutions or numerical simulation.
  • Feasibility question: Examples question whether equal total antenna or DoF counts guarantee feasibility when antenna distributions or user counts differ.
  • Approach: The proposed approach treats signal-space alignment as solvability of a multivariate polynomial system for K-user MIMO interference networks.

B. Interference Alignment in Signal Space - Beamforming and Zero Forcing Formulation

The formulation represents each user’s transmitted streams with beamforming and designs transmit and receive subspaces to satisfy zero-forcing constraints. Feasibility is then analyzed by counting independent polynomial equations and nonredundant variables, while accounting for basis invariance.

  • Beamforming and zero forcing: Each transmitter sends d[k] independently encoded streams through an M[k] × d[k] precoding matrix V[k].
  • Beamforming and zero forcing: Transmit filters maximize overlap among interference subspaces while receive filters preserve desired-signal independence, enabling receivers to zero-force interference.
  • Beamforming and zero forcing: For generic channels, the desired-signal full-rank condition is automatically satisfied when transmit and receive filters have rank d[k] and satisfy the interference constraints.
  • Equation and variable counting: The polynomial-system intuition classifies systems by comparing the number of equations with the number of variables, with equations exceeding variables indicating an improper system.
  • Beamforming and zero forcing: The alignment constraints require U[k]†H[kj]V[j] = 0 for every interfering transmitter j ≠ k.
  • Equation and variable counting: Transmit and receive beamforming vectors generate the alignment equations, whose total count is obtained from the pairwise interference-zero-forcing conditions.
  • Equation and variable counting: Counting variables requires removing superfluous degrees of freedom rather than treating every entry of each precoding filter as independent.
  • Basis representation: Right-multiplying a full-rank precoding matrix by an invertible matrix leaves its transmitted signal subspace unchanged, so a reduced basis representation can be used.

B. Proper System Characterization

The paper defines proper systems by requiring every equation subset to involve at least as many variables as equations. For symmetric systems, total equation and variable counts suffice, yielding antenna-based feasibility tests and DoF bounds.

  • Definition: A proper system requires every subset of equations to involve at least as many variables as equations.This formalizes the equation-variable criterion across all equation subsets.
  • Symmetric systems: For symmetric systems, comparing total equations with total variables suffices to determine properness.Symmetry makes subset deficiencies visible in the aggregate count.
  • Symmetric systems: M + N ≥ (K + 1)d antennas per user suffices for a proper symmetric K-user system achieving d DoF, with at least d antennas at each node.The antennas may be distributed arbitrarily between transmitter and receiver while preserving symmetry.
  • DoF bounds: For a proper (M × N, d)K system, the normalized DoF is upper bounded by the paper’s stated corollary.The bound is derived directly from the properness condition.
  • DoF bounds: When M = N, a proper system achieves no more than twice each user’s interference-free DoF.The paper contrasts this with the larger DoF factor available for diagonal time-varying channels.
  • Symmetric systems: Properness status is preserved within antenna-transfer groups under the stated dimensional conditions.The condition depends on M + N, allowing antennas to be transferred between transmitters and receivers.

D. Asymmetric Systems ΠK

For asymmetric networks, aggregate equation-variable counts can identify improper systems but may miss deficient equation subsets. The paper therefore checks subsets and illustrates infeasibility caused by an equation with no variables.

  • Asymmetric systems: In asymmetric systems, an improper total equation-variable count can suffice to establish infeasibility.The paper gives a system with 11 variables and 12 equations as an improper example.
  • Asymmetric systems: Bottleneck equations can be located by examining equations involving the fewest transmitter and receiver antennas.These equations contain the fewest variables and may determine properness.
  • Asymmetric systems: Subset checks are necessary because equal total counts can conceal an equation involving zero variables.The (2 × 1, 1)(1 × 2, 1) system has the same aggregate counts as a feasible comparison system but is improper.
  • Asymmetric systems: The paper also applies the properness condition to compare a feasible 2-user network with a 4-user network formed from two such network pairs.This example tests whether doubling users preserves the desired total DoF.

IV. NUMERICAL RESULTS

Numerical experiments evaluate interference percentage against total beams and support the paper’s properness predictions for single-beam cases. The results also show higher interference under excess DoF and certain antenna asymmetries.

  • Numerical validation: For single-beam cases, numerical results consistently find proper systems almost surely feasible and improper systems infeasible.The tests cover numerous symmetric and asymmetric interference-alignment problems.
  • Numerical validation: Zero interference at the expected-DoF point supports the claim that the tested proper networks are feasible.The figure also includes multi-beam numerical results, discussed separately in the paper.
  • Interference results: Nonzero interference after demanding excess total DoF indicates that alignment is impossible for that demanded DoF.The x-axis begins at each network’s expected total DoF.
  • Interference results: Systems with expected 4 total DoF show more interference than systems with expected 8 total DoF under excess-DoF demands.The reported comparison is based on the interference percentages in Fig. 2.
  • Interference results: Among systems with the same expected total DoF, fewer receiver-side antennas correspond to more interference in the reported comparison.The paper specifically compares (2 × 3, 1)2(3 × 2, 1)2 with (2 × 3, 1)4.
  • Polynomial-system framework: The paper frames properness as an extension of algebraic-geometry solvability intuition, while noting that multi-beam systems have dependent coefficients.Single-beam systems have independent coefficients, whereas repeated channel matrices create dependencies in multi-beam systems.
  • Polynomial-system framework: A polynomial’s support set consists of exponent vectors with nonzero coefficients.For fi = ci1x1 + ci2x1x2 + ci3, the support forms the vertices of a right triangle.

2) Common solutions of a polynomial system:

The paper characterizes common solutions of a multivariate polynomial system as points satisfying every equation simultaneously. It also defines polynomial degree through exponent sums.

  • Common solutions: A common solution is an n-dimensional point at which every polynomial in the system equals zero.The complete common-solution set is represented as SC = {S1, · · · , Ss}.
  • Common solutions: The system’s common solutions are enumerated as s points in the corresponding n-dimensional complex space.Each solution has coordinates (x1^k, · · · , xn^k).
  • Polynomial degree: The degree of each polynomial is defined from the exponent sums of its monomials.The supplied passage introduces degree notation and its exponent-based construction.

B. Dense and Sparse Polynomial Systems

Dense polynomial systems include all monomials up to each polynomial's degree, whereas sparse systems omit some monomials. Bezout's theorem gives the dense-system solution count, while Bernshtein's theorem provides a tighter count for sparse systems.

  • Dense polynomial systems contain monomials with all combinations of variable exponents up to each polynomial's degree.
  • Sparse polynomial systems have selected monomials with zero coefficients, producing fewer terms than dense systems.
  • 12 common solutions follow from Bezout's theorem for the dense system in Example 11.
  • 9 common solutions follow from Bernshtein's theorem for the corresponding sparse system, compared with Bezout's looser upper bound of 12.
  • Newton polytopes are lattice polytopes formed from exponent vectors of monomials with nonzero coefficients.

2) Mixed Volume and Minkowski Sum:

Mixed volume uses Minkowski sums of Newton polytopes to characterize sparse polynomial systems. Bernshtein's theorem equates the generic solution count with mixed volume, enabling feasibility tests for single-beam alignment systems.

  • Minkowski sums combine Newton polytopes by adding every element of their support sets.
  • Mixed volume is computed from volumes of Minkowski sums and is always nonnegative.
  • Bernshtein's theorem states that generic common solutions in (C*)^n equal the mixed volume of the Newton polytopes.
  • For dense systems, Bernshtein's mixed volume reduces to the product of the polynomial degrees, making Bezout's theorem a special case.
  • Facet-based computation can simplify high-dimensional mixed-volume evaluation, but detailed calculations and general algorithms remain cumbersome.
  • For single-beam systems, nonzero mixed volume implies almost-sure solvability and zero mixed volume implies almost-sure nonsolvability under generic coefficients.
  • The systems (2 × 3, 1)4 and (2 × 3, 1)2(3 × 2, 1)2 have mixed volumes 9 and 8, respectively, and are almost surely solvable.
  • The system (2 × 2, 1)3(3 × 5, 1) is improper and has mixed volume 0, so it is almost surely nonsolvable under independent random coefficients.

VII. NEW CLOSED FORM SOLUTIONS

The paper gives closed-form interference-alignment constructions for the asymmetric (2 × 3, 1)2(3 × 2, 1)2 system by sequentially imposing null-space and alignment conditions. The resulting beamforming filters are fully determined.

  • VII. NEW CLOSED FORM SOLUTIONS: The constructions exploit a shared eigenvector structure: aligning two interference vectors at two receivers yields an eigenvector solution.
  • A. Asymmetric (2 × 3, 1)2(3 × 2, 1)2 System: Transmitter 4 is parameterized in the null space of u[3]H[34], reducing its design from a 3 × 1 vector to a 2 × 1 vector.
  • A. Asymmetric (2 × 3, 1)2(3 × 2, 1)2 System: Transmitter 1 and transmitter 2 are chosen to align their interference at receivers 3 and 4.
  • A. Asymmetric (2 × 3, 1)2(3 × 2, 1)2 System: After transmit vectors v[1] and v[2] are determined, receive filters u[3] and u[4] are obtained by nulling the remaining interference.
  • A. Asymmetric (2 × 3, 1)2(3 × 2, 1)2 System: The same null-space reduction is applied to transmitter 3 using the null space of u[4]H[43].
  • A. Asymmetric (2 × 3, 1)2(3 × 2, 1)2 System: At receivers 1 and 2, the receive filters are reduced to 1 × 2 vectors by projecting into left null spaces determined by already-designed transmit vectors.
  • A. Asymmetric (2 × 3, 1)2(3 × 2, 1)2 System: The reduced alignment conditions become 2 × 2 matrix relations, with v′ obtained as an eigenvector and the remaining receive filters recovered afterward.
  • A. Asymmetric (2 × 3, 1)2(3 × 2, 1)2 System: The construction completes all transmit and receive beamforming filters for the asymmetric system.

B. Symmetric (2 × 3, 1)4 System

A direct closed-form expression for the (2 × 3, 1)4 system is difficult, so the paper derives it through an auxiliary system with one extra receive antenna. Eliminating the resulting extra variable yields a solution for the target system.

  • B. Symmetric (2 × 3, 1)4 System: The paper first solves the auxiliary (2 × 4, 1)(2 × 3, 1)3 system, which has one extra receive antenna and corresponding extra freedom.
  • B. Symmetric (2 × 3, 1)4 System: Choosing transmitter 1's beam randomly makes receivers 2, 3, and 4 discard its interference dimension, reducing them to 2-dimensional subspaces.
  • B. Symmetric (2 × 3, 1)4 System: The reduced transmitter-receiver pairs form a known 3-user interference channel with 2 antennas at each node.
  • B. Symmetric (2 × 3, 1)4 System: Receiver 1 uses its four antennas to zero-force all interference, so each user achieves 1 DoF in the auxiliary system.
  • B. Symmetric (2 × 3, 1)4 System: The extra receive-antenna variable u3 is selected through iterative equations rather than arbitrarily.
  • B. Symmetric (2 × 3, 1)4 System: Eliminating u3 by solving it in terms of other variables provides a solution for the (2 × 3, 1)4 system.

VIII. MULTI-BEAM CASES

Multi-beam feasibility is harder because coefficient dependencies prevent properness alone from characterizing solvability. The analysis therefore combines proper-system tests with general and cooperative information-theoretic outer bounds.

  • VIII. MULTI-BEAM CASES: Multi-beam polynomial systems can have dependent coefficients, so properness alone cannot determine feasibility.The resulting systems are not generic in the sense required by the relevant algebraic-geometry theorems.
  • VIII. MULTI-BEAM CASES: General DoF outer bounds include pairwise transmitter and receiver antenna constraints for every user pair.These bounds are derived from point-to-point and two-user MIMO interference-channel limits.
  • VIII. MULTI-BEAM CASES: A proper system can still be almost surely infeasible when it violates a general outer bound, as shown by the (3 × 3, 2)2 example.This example demonstrates that equation-variable counting is insufficient without information-theoretic constraints.
  • VIII. MULTI-BEAM CASES: Cooperative outer bounds test feasibility after grouping transmitters and receivers into cooperating parties.Violation for any such cooperation pattern implies almost-sure infeasibility.
  • VIII. MULTI-BEAM CASES: The (5 × 5, 2)4 system is proper, whereas the (5×5, 3)(5×5, 2)3 system is improper because Nv = 48 is less than Ne = 60.Theorem-based checks avoid testing all 2^Ne − 1 equation subsets in these examples.
  • VIII. MULTI-BEAM CASES: For multi-beam cases, numerical results indicate that adding general and cooperative outer bounds strengthens the connection between properness and feasibility.The conclusion also reports that improper systems are infeasible based on numerical observations.

APPENDIX

The appendix clarifies algebraic genericity through coefficient polynomials and algebraic independence. It connects the generic conditions in Bezout’s and Bernshtein’s theorems to independent random coefficients.

  • APPENDIX: The coefficient set is algebraically dependent when some coefficient polynomial vanishes identically on it; otherwise, it is algebraically independent.The appendix introduces this distinction for coefficients of f1, · · ·, fn.
  • APPENDIX: Bezout’s and Bernshtein’s theorems give exact common-solution counts when polynomial coefficients are generic.Bernshtein’s theorem is described through the mixed volume of the Newton polytopes.
  • APPENDIX: Genericity is defined through a coefficient polynomial whose nonvanishing guarantees a property of the polynomial system.A property holds generically when the relevant coefficient polynomial is nonzero.
  • APPENDIX: Independent random coefficients are almost surely generic because they are algebraically independent.The appendix states that the relevant coefficient polynomial is nonzero almost surely under independent random coefficients.
Loading 0911.4507v1…