MathJax

Friday, July 01, 2016

Spectral Theorem for Diagonalizable Matrices

It occurs to me that most presentation of the spectrum theorem only concerns orthonormal basis.  This is a more general result from Meyer.

Theorem
A matrix \( \mathbf{A} \in \mathbb{R}^{n\times x}\) with spectrum \(\sigma(\mathbf{A}) = \{ \lambda_1, \dotsc, \lambda_k \} \) is diagonalizable if and only if there exist matrices \(\{ \mathbf{G}_1, \dotsc, \mathbf{G}_k\} \) such that  \[ \mathbf{A} = \lambda_1 \mathbf{G}_1 + \dotsb + \lambda_k  \mathbf{G}_k \] where the \(\mathbf{G}_i\)'s have the following properties
  • \(\mathbf{G}_i\) is the projector onto \(\mathcal{N} (\mathbf{A} - \lambda_i \mathbf{I})  \) along \(\mathcal{R} ( \mathbf{A} - \lambda_i \mathbf{I} ) \). 
  • \(\mathbf{G}_i\mathbf{G}_j = 0 \) whenever \( i \neq j \)
  • \( \mathbf{G}_1 + \dotsb + \mathbf{G}_k = 1\)
The expansion is known as the spectral decomposition of \(\mathbf{A}\), and the \(\mathbf{G}_i\)'s are called the spectral projectors associated with \(\mathbf{A}\).

Note that being a projector \(\mathbf{G}_i\) is idempotent.
  • \(\mathbf{G}_i = \mathbf{G}_i^2\)
And since \(\mathcal{N}(\mathbf{G}_i) = \mathcal{R}(\mathbf{A} - \lambda_i \mathbf{I} ) \) and \(\mathcal{R}(\mathbf{G}_i) = \mathcal{N}(\mathbf{A} - \lambda_i \mathbf{I} ) \), we have the following equivalent complimentary subspaces
  • \(  \mathcal{R}(\mathbf{A} - \lambda_i \mathbf{I} ) \oplus \mathcal{N}(\mathbf{A} - \lambda_i \mathbf{I} ) \)
  • \(  \mathcal{R}(\mathbf{G}_i) \oplus \mathcal{N}(\mathbf{A} - \lambda_i \mathbf{I} ) \)
  • \(  \mathcal{R}(\mathbf{A} - \lambda_i \mathbf{I} ) \oplus  \mathcal{N}(\mathbf{G}_i) \)
  • \(  \mathcal{R}(\mathbf{G}_i)  \oplus  \mathcal{N}(\mathbf{G}_i) \)

Friday, June 24, 2016

Conference submission deadlines 2016

ICASSP 2017 - 2016/09/12
WCNC 2017 - 2016/09/30

Monday, June 06, 2016

Majorization and Schur-convexity

Majorization 

A real vector \( b = (b_1,\dotsc,b_n) \) is said to majorize \( a = ( a_1,\dotsc, a_n)  \), denote \( a \succ b\ \)  if

  1.  \( \sum_{i=1}^n a_i  = \sum_{i=1}^n b_i \), and
  2. \( \sum_{i=k}^n a_{(i)} \leq \sum_{i=k}^n b_{(i)} \), \( k = 2,\dotsc,n \)
where \( a_{(1)} \leq \dotsb \leq a_{(n)} \), \( b_{(1)} \leq \dotsb \leq b_{(n)} \) are \(a\) and \(b\) arranged in increasing order. 

A function \( \phi(a) \) symmetric in the coordinates of \( a = ( a_1, \dotsc, a_n ) \) is said to be Schur-concave if  \( a \succ b \) implies \( \phi(a) \ge \phi(b) \).  

A function \( \phi(a) \) is Schur-convex if \( -\phi(a) \) is Schur-concave.

Tuesday, May 03, 2016

Requirements for good parenting


  1. Keep my child's emotional love tank full - speak the five love languages.
    • physical touch
    • words of affirmation
    • quality time
    • gifts
    • acts of service
  2. Use the most positive ways I can to control my child's behavior: requests, gentle physical manipulation, commands, punishment, and behavior modification.
  3. Lovingly discipline my child.  Ask, "What does this child need?" and then go about it logically.
  4. Do my best to handle my own anger appropriately and not dump it on my child.  Be kind but firm.
  5. Do my best to train my child to handle anger maturely - the goal is sixteen and a half years. 
From the five love languages of children

Monday, April 11, 2016

RAII (Resource acquisition is initialization) definition

https://en.wikipedia.org/wiki/Resource_Acquisition_Is_Initialization

Thursday, January 14, 2016

UL/DL network duality for SINR metric

See Boche and Schubert's "A General Duality Theory for Uplink and Downlink Beamforming"

Tuesday, January 12, 2016

Notes on Recursive Least Squares (RLS)


Method of Least Squares
  • Assuming a multiple linear regression model, the method attempts to choose the tap weights to minimize the sum of error squares.
  • When the error process is white and zero mean, the least-squares estimate is the best linear unbiased estimate (BLUE)
  • When the error process is white Gaussian zero mean, the least-squares estimate achieves the Cramer-Rao lower bound (CRLB) for unbiased estimates, hence a minimum-variance unbiased estimate (MVUE)
Recursive Least Squares
  • Allows one to update the tap weights as the input becomes available.
  • Can incorporate additional constraints such as weighted error squares or a regularizing term, [commonly applied due to the ill-posed nature of the problem].
  • The inversion of the correlation matrix is replaced by a simple scalar division.
  • Initial correlation matrix provide a mean to specify regularization.
  • The fundamental difference between RLS and LMS: 
    • The step-size parameter \(\mu\) in LMS is replaced by \(\mathbf{\Phi}^{-1}(n)\), the inverse of the correlation matrix of the input \(\mathbf{u}(n)\), which has the effect of whitening the inputs.
  • The rate of convergence of RLS is invariant to the eigenvalue spread of the ensemble average input correlation matrix \(\mathbf{R}\)
  • The excessive mean-square error converges to zero if stationary environment is assumed and the exponential weight factor is set to \(\lambda=1\).

Tuesday, December 22, 2015

Notes on transform domain adaptation (LMS)

Transform domain adaptive filter (e.g. DFT-LMS, DCT-LMS)
  • Performance of LMS is sensitive to the eigenvalue spread of the input covariance matrix.
  • The smallest eigenvalue contribute to slower convergence and the largest eigenvalue limit the range of allowed step-sizes, thus limiting the learning abilities of the filter.
A DFT/DCT type transformation allows one to whiten the input sequence in the transform domain without the need to know the correlation matrix (e.g. using KLT) of the sequence which may not be stationary.

[Hodgkiss, 1979] has shown the conditions under which time domain and frequency domain processing is equivalent.  
[Beaufays, 1995] showed analytically the eigenvalue distributions of a markov-1 sequence to have asymptotic eigenvalue spread of  [interesting matrix theory]
\[ \left( \frac{1+\rho}{1-\rho} \right)^2, \quad \text{before transformation} \] 
\[ \left( \frac{1+\rho}{1-\rho} \right), \quad \text{after DFT and power normalization} \] 
\[ (1+\rho), \quad \text{after DCT and power normalization} \]

Monday, December 21, 2015

Random sequence whitening


  • Orthogonal decomposition (e.g. EVD) and triangular decomposition (e.g. LDU) decorrelate a signal sequence.
  • LDU decomposition allows us to whiten a signal causally (since \(\mathbf{B}=\mathbf{L}^{-1}\) is a causal linear transform).

Notes on Discrete Karhunen-Loeve Transform (DKLT) and DFT


  • In general, the DKLT is obtained from eigenvalue decomposition.
  • The correlation matrix of a stationary process is Toeplitz.
  • If the autocorrelation sequence of a random process is periodic with fundamental period \(M\), its correlation matrix becomes circulant.
  • The DFT provides the DKLT of periodic random sequences.
    • This can be easily seen because DFT defines the complete set of eigenvectors for all circulant matrices.

Thursday, December 10, 2015

Notes on Globecom 2015


Monday 12/7/2015 

Morning session 
  • Suppression of Analog Self-Interference Canceller Nonlinearities in MIMO Full Duplex 
    • Use of nonlinear modeling to cancel nonlinear behavior of the RF chain
  • Receive Spatial Modulation (Marco Di Renzo) 
    • New ideas for MIMO Broadcast Channel 
  • A 60GHz LOS MIMO Backhaul Design Combining Spatial Multiplexing and Beamforming for a 100Gbps Throughput (Gerhard Fettweis' group)
    • Deterministic Spatial Multiplexing (Antenna spacing determined by the distance between TX and RX)
Noon session (mmWave)
  • Adaptive One-bit Compressive Sensing with Application to Low-Precision Receivers at mmWave (joint work University of Vigo, Spain and Robert Heath)
    • Compressive sensing for estimating channel of 1-bit receiver
Afternoon session (Massive MIMO)
  • Exploiting the Tolerance of Massive MIMO to Incomplete CSI for Low-Complexity Transmission (UCL)
    • Exploit antenna correlation by training a subset of antennas and interpolate missing information.  (Perhaps CS based schemes can be used?)
  • Downlink Performance and User Scheduling of HetNet with Large-Scale Antenna Arrays (University of Victoria)
    • Lower bound analysis on Hetnet.  (Useful technique)
  • Large System Analysis of Base Station Cooperation in the Downlink (Luca Sanguinetti, Couillet and Debbah)
    • New RMT results for DL BS cooperation with imperfect CSI 
Tuesday 12/8/2015 

Morning session (Massive MIMO)
  • Polynomial-Expansion Multi-Cell Aware Detector for Uplink Massive MIMO Systems with Imperfect CSI (Germany)
    • replacing matrix inverse with polynomial expansion
  • Joint Use of H-inf Criterion in Channel Estimation and Precoding to Mitigate Pilot Contamination in Massive MIMO Systems (University of Northeastern, China)
    • H-inf Criterion used to design CE and Precoding (minimax like criterion, minimize worst case penalty)
  • Location-Aided Pilot Contamination Elimination for Massive MIMO Systems (Chalmers, Sweden)
    • estimate AoA and AS to compute Covariance matrix.
  • Data-Assisted Massive MIMO Uplink Transmission with Large Backhaul Cooperation Delay: Scheme Design and System-Level Analysis (Very good analysis)
    • Successively use data to improve channel estimation.   
    • Develop network model with fixed BS location using stochastic geometry
    • Shifted Zadoff Chu sequence used (do not reuse pilots)
Noon session 
  • Maximal Ratio Transmission in Wireless Poisson Networks under Spatially Correlated Fading Channels
    • Stochastic geometry.  Correlated channel.  Spatial correlation is SINR dependent.
  • Performance Analysis of Single-Carrier Modulation with Correlated Large-Scale Antennas (Geoffrey Li, Georgia Tech) 
    • Propose SC over OFDM in massive MIMO.  No equalizer under the condition of i.i.d channel.
Afternoon session
  • Multi-switch for antenna selection in massive MIMO
    • binary switching in antenna selection (have small loss in capacity)
  • A Multi-cell MMSE Precoder for Massive MIMO Systems and New Large System Analysis (Emil Bjornson)  Good analysis
    • Multicell MMSE precoder for TDD massive MIMO using idea of Pilot reuse.  Exploit UL/DL duality to come up with precoder design that spans B directions only.  
  • Harmonized Cellular and Distributed Massive MIMO: Load Balancing and Scheduling (DOCOMO)
    • Distributed massive MIMO with Hetnet, scheduling using blanking etc.  
    • research has industry knowledge 

Thursday, December 03, 2015

Multi-cluster massive MIMO

Ideas 
  • [12/3/2015] It might be worthwhile to look into the design of the transmit unitary matrix.
Challenges
  • When interfering channel is present, any use of the interfering channel will add to the noise temperature of the environment.

Key Concepts
  • Successive decoding achieves the capacity region of degraded broadcast channel.  
    • Scalar broadcast channel is a degraded broadcast channel.
  • MISO channel: With only covariance feedback, water filling along the eigenvectors of the channel covariance achieve capacity.  Specifically independent complex circular Gaussian inputs along the eigenvectors of \(\Sigma\) is optimal.

Tuesday, November 24, 2015

Quasiconvex functions

A function \(f\) is quasiconvex iff \(\mathbf{dom} f\) is convex and for any \(x,y \in \mathbf{dom} f\) and \(0\leq \theta \leq 1\)
\[  f(\theta x + (1-\theta) y) \leq \max\{ f(x), f(y) \}\]  A continuous function \(f: \mathbf{R} \rightarrow \mathbf{R}\) is quasiconvex iff at least one of the following conditions holds

  • \(f\) is nondecreasing
  • \(f\) is nonincreasing
  • there is a point \(c\in \mathbf{dom} f\) such that for \(t \leq c\), \(f\) is nonincreasing, and for \(t \ge c\), \(f\) is nondecreasing.

First order conditions

A continuous differentiable function \(f: \mathbf{R}^n \rightarrow \mathbf{R}\) is quasiconvex iff \(\mathbf{dom} f\) is convex and for all \(x,y\in \mathbf{dom}f\) 
\[ f(y) \leq f(x) \Rightarrow \nabla f(x)^T (y-x) \leq 0 \]
Operations that preserve quasiconvexity
  • nonnegative weighted maximum
    The function \[ f(x) = \sup_{y\in C} (w_y g_y(x) ) \]  where \(w_y \ge 0\) and \(g_y(x)\) is a parameterized family of quasiconvex functions.
  • composition
    • if \(g\) is quasiconvex and \(h\) is nondecreasing then, \(f = h \circ g\) is quasiconvex
    • composition of a quasiconvex function with an affine or linear-fractional transformation yields a quasiconvex function.
  • minimization
    if \(f(x,y)\) is quasiconvex jointly in \(x\) and \(y\) and \(C\) is a convex set, then the function
    \[ g(x) = \inf_{y\in C} f(x,y)\] is quasiconvex.

Wednesday, November 18, 2015

Gaussian interference channel


The sum capacity is known for two special cases:

Strong interference: Capacity is achieved by decoding and canceling the interference before decoding the desired signal.  The condition is defined as \(I_2 \ge S_1\) and \(I_1 \ge S_2\)
\begin{align*}
R_1 & \leq C(S_1), \\
R_2 & \leq C(S_2), \\
R_1 + R_2 & \leq \min \lbrace C(S_1+I_1), C(S_2+I_2)  \rbrace
\end{align*}

Weak interference:  Capacity is achieved by treating interference as Gaussian noise
\[  C_{sum} = C \left( \frac{S_1}{1+I_1} \right) + C \left( \frac{S_2}{1+I_2} \right)  \]


Gaussian broadcast channel

Two users case
Scalar Gaussian broadcast channel belongs to the class of degraded broadcast channel.  (The users can be absolutely ranked by their channel strength)  

When the transmitter has more than one antenna, the Gaussian broadcast channel is non-degraded.

Sender of power \(P\) transmit to two receivers, one with Gaussian noise power \(N_1\) and the other with \(N_2\).  assume \(N_1 < N_2\).   The capacity region is
\begin{align*}
R_1 &< C \left(\frac{\alpha P}{N_1}\right) \\
R_2 &< C \left(\frac{(1-\alpha) P}{\alpha P + N_2}\right) \\
\end{align*} where \(0 \leq \alpha \leq 1 \)

The weaker receiver \(Y_2\) decodes its own message treating the other user's message as interference.  The stronger receiver \(Y_1\) decodes \(Y_2\)'s message and cancels it before decoding his own.

Note:  The role of transmitter side information reduces with the growth in the number of TX antennas.  With either CSIT or CDIT and under the ZMSW model the asymptotic growth is linear as \( \mathcal{C} \min(M,K) \).


Monday, November 02, 2015

weighted arithmetic-geometric mean inequality

Generalized form of the AM-GM inequality
\[ \sum_i \alpha_i v_i \ge \prod_i v_i^{\alpha_i} \] where \(\mathbf{v} \succ 0\) and \(\mathbf{\alpha} \succeq 0,\; \mathbf{1}^T\mathbf{\alpha} = 1\).

Tuesday, October 27, 2015

Karush-Kuhn-Tucker conditions for non-convex problems

Consider a problem (ICP) with equality and inequality constraints:
\begin{align*}
\text{minimize}\quad &f(x) \\
\text{subject to}\quad &h_i(x) = 0,\quad i=1,\dotsc,m\\
                                    &g_j(x) \le 0,\quad j=1,\dotsc,r
\end{align*} where \(f,\;h_i,\; g_j\) are continuously differentiable functions from \(\mathbb{R}^n\) to \(\mathbb{R}\).

With Lagrange function
\[L(x,\lambda,\mu) = f(x) + \sum_{i=1}^m \lambda_i h_i(x) + \sum_{j=1}^r \mu_j g_j(x)\]
Define the set of active inequality constraints:
\[ A(x) =\{ j \;|\; g_j(x) = 0 \}\] A feasible vector \(x\) is regular if the equality constraint gradients \(\nabla h_i(x),\; i=1,\dotsc,m\), and the active inequality constraint gradients \(\nabla g_j(x),\; j\in A(x)\) are linearly independent.

KKT optimality conditions

KKT necessary conditions for regular \(x^*\)

Let \(x^*\) be a local minimum of the problem
\begin{align*}
\text{minimize}\quad &f(x) \\
\text{subject to}\quad &h_i(x) = 0,\quad  i=1,\dotsc,m\\
                                    &g_j(x) \le 0,\quad j=1,\dotsc,r
\end{align*} where \(f,\;h_i,\; g_j\) are continuously differentiable functions from \(\mathbb{R}^n\) to \(\mathbb{R}\) and \(x^*\) is regular. There exist unique Lagrange multiplier vectors \(\lambda^* = (\lambda^*_1,\dotsc,\lambda^*_m)\), \(\mu^*=(\mu^*_1,\dotsc,\mu^*_r)\) such that
\begin{align*}
\nabla_x L(x^*,\lambda^*,\mu^*) = 0, \\
\mu^*_j\ge 0, \quad &j=1,\dotsc,r, \\
\mu^*_j=0,\quad &\forall j \notin A(x^*)
\end{align*}  Note: The condition can be written as
\[\mu^*_j g_j(x^*) = 0, \quad j=1,\dotsc,r\] and aptly referred to as complementary slackness condition.

If in addition \(f\), \(h\), and \(g\) are twice continuously differentiable, there holds
\[ y^T \nabla^2_{xx} L(x^*,\lambda^*,\mu^*)y \ge 0\] for all \(y\in \mathbb{R}^n\) such that
\begin{align*}
\nabla h_i(x^*)^T y &= 0, \quad \forall i=1,\dotsc,m \\
\nabla g_j(x^*)^T y &= 0, \quad \forall j \in A(x^*)
\end{align*}


Wednesday, October 14, 2015

Braess' paradox

An interesting anomaly in non-cooperative behavior.  (An example where Nash equilibrium is not optimal) See link