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} \]

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.

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 

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.

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.

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) \).

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\).

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*}

Braess' paradox

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

Weak and strong alternatives

Weak alternatives

• Two systems of inequalities are called weak alternatives if at most one of the two is feasible.
• This is true whether or not the inequalities of system 1 are convex (i.e. \(f_i\) convex, \(h_i\) affine)
• System 2 is always convex (\(g\) concave and \(\lambda_i\ge 0\) are convex)

Lagrange duality theory can be applied to the problem of determining feasibility of a system of inequalities and equalities
\begin{equation}f_i(x) \leq 0, \; i=1,\cdots,m,\quad h_i(x)=0,\; i=1,\cdots,p
\end{equation}
The above can be posed as the standard problem with objective \(f_0=0\):
\begin{align*}
\text{minimize} \quad &0\\
\text{subject to}\quad &f_i(x) \leq 0, \quad i=1,\cdots,m \\
&h_i(x) = 0, \quad i=1,\cdots,p
\end{align*}
This problem has optimal value
\[ p^* = \begin{cases}
                  0\quad &\text{if system is feasible}\\
                 \infty\quad &\text{if system is infeasible}
              \end{cases}
\]
We associate with the inequality system the dual function
\[ g(\lambda,\nu)= \inf_{x\in\mathcal{D}} \left(\sum_{i=1}^m \lambda_i f_i(x) + \sum_{i=1}^p \nu_i h_i(x) \right) \]
Note that the dual function has is positive homogeneous, i.e. that for \(\alpha > 0, \; g(\alpha\lambda,\alpha\nu) = \alpha g(\lambda,\nu)\).   The dual problem of maximizing \(g(\lambda,\nu) \; s.t. \; \lambda \succeq 0\) has the optimal value
\[
d^* = \begin{cases}
           \infty \quad &\lambda \succeq 0, \; g(\lambda,\nu) \gt 0 \text{ is feasible}\\
            0       \quad &\lambda \succeq 0, \; g(\lambda,\nu) \gt 0 \text{ is infeasible}
          \end{cases}
\]
From weak duality \(d^*\leq p^*\) and the above facts, we can conclude that the inequality system
\begin{equation} \lambda\succeq 0, \quad g(\lambda,\nu) \gt 0\end{equation} is feasible \(d^*=\infty\), then the inequality system is infeasible (since \(p^* = \infty\))

A solution to the dual function is a certificate of infeasibility of the system.  To summarize:

• feasibility of system 2 implies infeasibility of system 1
• feasibility of system 1 implies infeasibility of system 2

Strong alternatives

When the original inequality system is convex, and some type of constraint qualification holds, then the pairs of weak alternatives becomes strong alternatives, which means exactly one of the two alternatives holds.

If system 1 is convex, it can be expressed as
\[f_i(x) \leq 0, \; i=1,\dotsm,m,\quad Ax=b, \; A\in \mathbf{R}^{p\times n}\]
This system and its alternative
\[ \lambda\succeq 0,\quad g(\lambda,\nu) \gt 0\]
are strong alternatives provided there exists an \(x\in \text{relint } \mathcal{D}\) with \(Ax=b\) and the optimal value \(p^*\) is attained.  [More on that later...]

See Farkas' lemma

Karush-Kuhn-Tucker (KKT) conditions

If strong duality (with zero duality gap) holds and \(x,\lambda,\nu\) - possibly more than one pair - are optimal (see previous post), and the problem has differentiable \(f_i, h_i\), it must satisfy the KKT conditions: [necessary condition]

1. primal constraints: \(f_i(x)\leq 0, i=1,\cdots,m, \; h_i(x) = 0, i=1,\cdots,p\)
2. dual constraints: \(\lambda\succeq 0\)
3. complementary slackness: \(\lambda_i f_i(x) = 0, i=1,\cdots,m \)
4. gradient of Lagrangian with respect to \(x\) vanishes:
   \[\nabla f_0(x) + \sum_{i=1}^m \lambda_i \nabla f_i(x) + \sum_{i=1}^p \nu_i\nabla h_i(x) = 0\]

For convex problems

Key: When the primal problem is convex, the KKT conditions are also sufficient for points to be primal and dual optimal.

If \(\tilde{x},\tilde{\lambda},\tilde{\nu}\) satisfy KKT for a convex problem (i.e. \(f_i\) convex, \(h_i\) affine).  Then they are optimal, with zero duality gap:

• from complementary slackness: \(f_0(\tilde{x})=L(\tilde{x},\tilde{\lambda},\tilde{\nu})\)
• from 4th condition (and convexity): \(g(\tilde{x},\tilde{\lambda},\tilde{\nu}) =L(\tilde{x},\tilde{\lambda},\tilde{\nu})\)

hence, \(f_0(\tilde{x}) = g(\tilde{x},\tilde{\lambda},\tilde{\nu})\)

If Slater's condition is satisfied:

\(x\) is optimal iff there exist \(\lambda,\nu\) that satisfy KKT conditions

• Slater implies strong duality, therefore dual optimum is attained
• generalizes optimality condition \(\nabla f_0(x) = 0\) for unconstrained problem

Key: Many algorithms for convex optimization are conceived as methods for solving the KKT conditions.

Slater's condition

If the primal problem is convex i.e. of the form
\begin{align*}
\text{minimize}\quad &f_0(x) \\
    \text{subject to}\quad &f_i(x) \leq 0, \quad i = 1,\cdots,m, \\
                                         &Ax=b
\end{align*} with \(f_0,\cdots,f_m\) convex, and if there exists a point that is strictly feasible, or more precisely an \(x\in \text{relint }\mathcal{D}\) such that

\[ f_i(x) \lt 0, \quad i=1,\cdots,m, \quad Ax=b.\]

Strong duality holds if the above condition is met.
Also, the dual optimum is attained \(d^*\gt -\infty\)

Notes on duality

Given a standard form problem (not necessarily convex)
\begin{align*}
\text{minimize} \quad  &f_0(x) \\
\text{subject to} \quad &f_i(x)\leq 0, &i=1,\cdots,m \\
                            &h_i(x) = 0,    &i=1,\cdots,p
\end{align*}
variable \(x\in \mathbb{R}^n\), domain \(\mathcal{D}\), optimal value \(p^*\)
with Lagrangian:
\[ L(x,\lambda,\nu) = f_0(x) + \sum_{i=1}^m \lambda_i f_i(x) + \sum_{i=1}^p \nu_i h_i(x) \]
and the (Lagrange) dual function:
\[ g(\lambda,\nu) = \inf_{x\in \mathcal{D}} L(x,\lambda,\nu)\]
Properties:

• \(g\) is concave over \(\lambda, \nu\) since it is the infimum of a family of affine functions.
• Lower bound property: if \(\lambda \succeq 0\) then \(g(\lambda,\nu) \leq p^*\)

since, if \(\tilde{x}\) is feasible and \(\lambda \succeq 0\), then
\[ g(\lambda,\nu) = \inf_{x\in \mathcal{D}} L(x,\lambda,\nu) \leq L(\tilde{x}, \lambda, \nu) \leq f_0(\tilde{x})\] minimizing over all feasible \(\tilde{x}\) gives \( g(\lambda,\nu) \leq p^*\)

Lagrange dual and conjugate function

Given an optimization problem with linear inequality and equality constraints
\begin{align*}
     \text{minimize}\quad &f_0(x) \\
     \text{subject to}\quad &Ax\preceq b \\
                                 &Cx=d.
\end{align*}
Using the definition of \(f^* = \sup_{x\in \text{dom }f} (y^T x - f(x))\), we can write the dual function as:
\begin{align*}
    g(\lambda,\nu)\quad &= \quad \underset{x}{\inf} (f_0(x) + \lambda^T (Ax-b) + \nu^T(Cx=d)) \\
                             &= \quad -b^T \lambda - d^T \nu + \underset{x}{\inf} (f_0(x) + (A^T \lambda + C^T \nu)^T x)\\
                             &= \quad -b^T \lambda - d^T \nu - f^* (-A^T \lambda - C^T \nu)
\end{align*} with domain
\[ \text{dom }g = \{ (\lambda,\nu) \;|\; -A^T \lambda - C^T \nu \in \text{dom } f_0^* \} \]

• simplifies derivation of dual if conjugate of \(f_0\) is known

The dual problem (finding the greatest lower bound for the primal problem)
\begin{align*}
    \text{maximize}\quad &g(\lambda,\nu) \\
    \text{subject to}\quad  &\lambda \succeq 0
\end{align*}

• a convex optimization problem; optimal value denoted \(d^*\)
• \(\lambda,\nu\) are dual feasible if \(\lambda \succeq 0, (\lambda,\nu)\in \text{dom }g\)

Weak duality: \(d^* \leq p^*\)

• always holds (for convex and nonconvex problems)
• can be used to find lower bounds for difficult problems

Strong duality: \(d^* = p^*\) (zero duality gap)

• does not hold in general
• (usually) holds for convex problems
• constraint qualifications assert conditions that guarantee strong duality in convex problems (e.g. Slater's constraint qualification)

Notes on dual norm

Dual norm is defined as
\[ \|z\|_* = \sup \{z^Tx \;|\; \|x\| \leq 1\}\] The dual norm can be interpreted as the operator norm of \(z^T\), interpreted as a \(1\times n\) matrix with the norm \(\|\cdot\|\) on \(\mathbf{R}^n\).

From the definition of dual norm we obtain the inequality
\[ z^Tx \leq \|x\| \|z\|_*\]
The conjugate of any norm \(f(x)=\|x\|\) is the indicator function of the dual norm unit ball
\[f^*(y) = \left\{ \begin{array}
                             00      & \|y\|_* \leq 1 \\
                             \infty     & \text{otherwise}
                         \end{array}
 \right. \]
Proof. If \(\|y\|_* \gt 1\), then by definition of the dual norm, there is a \(z\in \mathbf{R}^n\) with \(\|z\| \leq 1\) and \(y^T z \gt 1\).  Taking \(x=tz\) and letting \(t \rightarrow \infty\), we have
\[ y^T x - \|x\| = t(y^Tz - \|z\|) \rightarrow \infty\] which shows that \(f^*(y) = \infty\).  Conversely, if \(\|y\|_*\leq 1\), then we have \(y^Tx \leq \|x\| \|y\|^*\) for all \(x\), which implies for all \(x\), \(y^Tx - \|x\| \leq 0\).  Therefore \(x=0\) is the value that maximizes \(y^Tx - \|x\|\), with maximum value 0.

Schur complement: characterizations of positive definiteness for block matrices

Let a block matrix \(X\in \mathbf{S}^n\) be partitioned as

\[ X = \begin{bmatrix}
                 A      &B \\
                 B^T  &C
           \end{bmatrix} \] where \(A\in \mathbf{S}^k\).  If \(\det A \neq 0\), the schur complement is
\[ S =C - B^TA^{-1}B \] The following characterizations of positive definiteness can be derived

• \(X\succ 0\) iff \(A\succ 0\) and \(S\succ 0\)
• If \(A\succ 0\), then \(X\succeq 0\) iff \(S\succeq 0\)

Example:
\begin{align*}
&A^TA \preceq t^2I, \quad &t\ge 0 \\
\Longleftrightarrow \quad &tI-t^{-1}A^T I A \succeq 0, \quad &t\ge 0 \\
\Longleftrightarrow \quad &
  \begin{bmatrix}
     tI & A \\
     A^T & tI
  \end{bmatrix} \succeq 0
\end{align*}

Notes on optimization problem

Optimality criterion for differentiable \(f_0\)
Given a convex optimization problem with objective \(f_0\).  \(x\) is optimal iff it is feasible and
\[ \nabla f_0(x)^T (y-x) \ge 0 \quad \text{for all feasible } y \]

if \(\nabla f_0(x) \neq 0 \), it means that \( -\nabla f_0(x) \) defines a supporting hyperplane to the feasible set at \(x\).

Unconstrained problem: \(x\) is optimal iff
\[ x\in \text{dom }f_0, \quad \nabla f_0(x) = 0 \]
Equality constrained problem:
\[ \text{minimize } f_0(x) \quad \text{ subject to } Ax=b  \]
\(x\) is optimal iff there exists a \(\nu\) such that
\[ x\in \text{dom }f_0, \quad Ax=b, \quad \nabla f_0(x)+A^T\nu = 0\]
Note: Lagrange multiplier optimality condition.

Minimization over nonnegative orthant
\[ \text{minimize } f_0(x) \quad \text{ subject to } x\succeq 0  \]
\(x\) is optimal iff
\[ x\in\text{dom }f_0, \quad x\succeq 0, \quad  \left\{ \begin{array}{lr}
                                                                                                \nabla f_0(x)_i \ge 0, \quad &x_i = 0  \\
                                                                                                \nabla f_0(x)_i = 0, \quad &x_i \ge 0
                                                                                      \end{array} \right.   \]
Note: The last condition is a complementarity condition.

Notes on conjugate function (Fenchel conjugate)

The conjugate function (Fenchel conjugate)

• Counterpart to Fourier transform in Convex Analysis

The conjugate of \(f\) (\(f\) not necessarily convex):

\[ f^*(y) = \underset{x\in \text{dom }f}{\sup} (y^Tx - f(x)) \]

The domain of \(f^*\) consists of \(y\in \mathbb{R}^n\) for which the supermum is finite, i.e. for which the difference \(y^T x - f(x)\) is bounded above on \(\text{dom }f\).

\(f^*\) is convex, since it is the pointwise supremum of a family of affine functions of \(y\).

Examples:

• Affine function. \(f(x)=ax+b\).  \(f^*(y) = yx-ax-b = (y-a)x-b\).  

\[ f^*(y)  =  \left\{ \begin{array}
                                     -b    &y=a\\
                                   \infty &\text{otherwise}
                              \end{array}  \right. \] with \(\text{dom }f^* = \{a\}\).

• Negative logarithm. \(f(x) = -\log x\), with \(\text{dom }f=\mathbb{R}_{++}\).  

The function \(xy + \log x\) is unbound above if \(y\ge 0\) and reaches its max at \(x=-1/y\) otherwise.
\[ f^*(y) =  \left\{ \begin{array}
                                   -1-\log (-y)    &y\lt 0\\
                                   \infty           &\text{otherwise}
                              \end{array}  \right. \] with \(\text{dom }f^* = \{y\; |\; y\lt 0 \}\)

Fenchel's inequality

Fenchel's inequality can be obtained from the definition of conjugate function

\[  f(x) + f^*(y) \ge x^T y , \quad \forall x,y\]
since for each \(y\),
\[  f^*(y) \ge x^Ty - f(x) \Leftrightarrow  f(x) + f^*(y) \ge x^Ty \]

Notes on convex functions

Basic Properties

[TODO]

Examples

• Affine functions are both convex and concave
• All norms are convex (e.g. Frobenius norm, Spectral norm)
• Max function \(f(x) = \max_i x_i\) is convex on \(\mathbb{R}^n\)
• Quadratic-over-linear function \(f(x,y)=x^2/y\) is convex on \(\text{dom }f=\mathbb{R}\times\mathbb{R}_{++}\)
• Log-sum-exp \(f(x)=\log \sum^n_{i=1}e^{x_i}\) is convex on \(\mathbb{R}^n\)
• Geometric mean \(f(x)=(\prod^n_{i=1}x_i)^{1/n}\) is concave on \(\text{dom }f=\mathbb{R}^n_{++}\)
• Log-det is concave on \(\text{dom }f=\mathbf{S}^n_{++}\)

Restriction of a convex function to a line

\(f:\mathbb{R}^n \rightarrow \mathbb{R}\) is convex iff the function \(g:\mathbb{R} \rightarrow \mathbb{R}\), 

\[ g(t) = f(x+tv), \quad \text{dom } g = \{ t\; |\; x + tv \in \text{dom } f \} \]

is convex in \(t\) for any \(x \in  \text{dom } f\), \(v \in \mathbf{R}^n\)

Upshot: can check convexity of \(f\) by checking convexity of functions of one variable.

Epigraph and sublevel set 

\(\alpha\)-sublevel set of \(f:\mathbb{R}^n \rightarrow \mathbb{R}\), is defined as all x for which the value of \(f(x)\) is less then \(\alpha\)

\[ C_\alpha = \{ x \in \text{dom } f \; | \; f(x) \leq \alpha \} \]

Property: sublevel sets of convex functions are convex (converse is false)

epigraph of \(f:\mathbb{R}^n \rightarrow \mathbb{R}\):

\[ \text{epi } f = \{ (x,t) \in \mathbb{R}^{n+1} \; | \; x \in \text{dom } f, f(x) \leq t \} \]

Property: \(f\) is convex iff  \(\text{epi }f\) is a convex set

Operations that perserve convexity

methods for establishing convexity of a function

1. verify definition (often simplified by restricting to a line)
2. for twice differentiable functions, show \(\nabla^2 f(x) \succeq 0\)
3. show that \(f\) is obtained from simple convex functions by operations that preserve convexity
• nonnegative weighted sum
• composition with affine function
• pointwise maximum and supremum
• composition
• minimization
• perspective