\(
\newcommand{\A} {\mathbb{A}}
\newcommand{\rma} {\mathrm{a}}
\newcommand{\rmA} {\mathrm{A}}
\newcommand{\ba} {\mathbf{a}}
\newcommand{\bA} {\mathbf{A}}
\newcommand{\cA} {\mathcal{A}}
\newcommand{\bcA} {\boldsymbol{\cA}}
\newcommand{\tnsrA} {\underline{\bA}}
\newcommand{\wta} {\widetilde{a}}
\newcommand{\wtA} {\widetilde{A}}
\newcommand{\wtrma} {\widetilde{\rma}}
\newcommand{\wtrmA} {\widetilde{\rmA}}
\newcommand{\wtba} {\widetilde{\ba}}
\newcommand{\wtbA} {\widetilde{\bA}}
\newcommand{\wha} {\widehat{a}}
\newcommand{\whA} {\widehat{A}}
\newcommand{\whrma} {\widehat{\rma}}
\newcommand{\whrmA} {\widehat{\rmA}}
\newcommand{\whba} {\widehat{\ba}}
\newcommand{\whbA} {\widehat{\bA}}
\newcommand{\whcA} {\widehat{\cA}}
\newcommand{\whtnsrA} {\widehat{\tnsrA}}
\newcommand{\B} {\mathbb{B}}
\newcommand{\rmb} {\mathrm{b}}
\newcommand{\rmB} {\mathrm{B}}
\newcommand{\bb} {\mathbf{b}}
\newcommand{\bB} {\mathbf{B}}
\newcommand{\cB} {\mathcal{B}}
\newcommand{\bcB} {\boldsymbol{\cB}}
\newcommand{\tnsrB} {\underline{\bB}}
\newcommand{\wtb} {\widetilde{b}}
\newcommand{\wtB} {\widetilde{B}}
\newcommand{\wtrmb} {\widetilde{\rmb}}
\newcommand{\wtrmB} {\widetilde{\rmB}}
\newcommand{\wtbb} {\widetilde{\bb}}
\newcommand{\wtbB} {\widetilde{\bB}}
\newcommand{\whb} {\widehat{b}}
\newcommand{\whB} {\widehat{B}}
\newcommand{\whrmb} {\widehat{\rmb}}
\newcommand{\whrmB} {\widehat{\rmB}}
\newcommand{\whbb} {\widehat{\bb}}
\newcommand{\whbB} {\widehat{\bB}}
\newcommand{\whcB} {\widehat{\cB}}
\newcommand{\whtnsrB} {\widehat{\tnsrB}}
\newcommand{\C} {\mathbb{C}}
\newcommand{\rmc} {\mathrm{c}}
\newcommand{\rmC} {\mathrm{C}}
\newcommand{\bc} {\mathbf{c}}
\newcommand{\bC} {\mathbf{C}}
\newcommand{\cC} {\mathcal{C}}
\newcommand{\bcC} {\boldsymbol{\cC}}
\newcommand{\tnsrC} {\underline{\bC}}
\newcommand{\wtc} {\widetilde{c}}
\newcommand{\wtC} {\widetilde{C}}
\newcommand{\wtrmc} {\widetilde{\rmc}}
\newcommand{\wtrmC} {\widetilde{\rmC}}
\newcommand{\wtbc} {\widetilde{\bc}}
\newcommand{\wtbC} {\widetilde{\bC}}
\newcommand{\whc} {\widehat{c}}
\newcommand{\whC} {\widehat{C}}
\newcommand{\whrmc} {\widehat{\rmc}}
\newcommand{\whrmC} {\widehat{\rmC}}
\newcommand{\whbc} {\widehat{\bc}}
\newcommand{\whbC} {\widehat{\bC}}
\newcommand{\whcC} {\widehat{\cC}}
\newcommand{\whtnsrC} {\widehat{\tnsrC}}
\newcommand{\D} {\mathbb{D}}
\newcommand{\rmd} {\mathrm{d}}
\newcommand{\rmD} {\mathrm{D}}
\newcommand{\bd} {\mathbf{d}}
\newcommand{\bD} {\mathbf{D}}
\newcommand{\cD} {\mathcal{D}}
\newcommand{\bcD} {\boldsymbol{\cD}}
\newcommand{\tnsrD} {\underline{\bD}}
\newcommand{\wtd} {\widetilde{d}}
\newcommand{\wtD} {\widetilde{D}}
\newcommand{\wtrmd} {\widetilde{\rmd}}
\newcommand{\wtrmD} {\widetilde{\rmD}}
\newcommand{\wtbd} {\widetilde{\bd}}
\newcommand{\wtbD} {\widetilde{\bD}}
\newcommand{\whd} {\widehat{d}}
\newcommand{\whD} {\widehat{D}}
\newcommand{\whrmd} {\widehat{\rmd}}
\newcommand{\whrmD} {\widehat{\rmD}}
\newcommand{\whbd} {\widehat{\bd}}
\newcommand{\whbD} {\widehat{\bD}}
\newcommand{\whcD} {\widehat{\cD}}
\newcommand{\whtnsrD} {\widehat{\tnsrD}}
\newcommand{\E} {\mathbb{E}}
\newcommand{\rme} {\mathrm{e}}
\newcommand{\rmE} {\mathrm{E}}
\newcommand{\be} {\mathbf{e}}
\newcommand{\bE} {\mathbf{E}}
\newcommand{\cE} {\mathcal{E}}
\newcommand{\bcE} {\boldsymbol{\cE}}
\newcommand{\tnsrE} {\underline{\bE}}
\newcommand{\wte} {\widetilde{e}}
\newcommand{\wtE} {\widetilde{E}}
\newcommand{\wtrme} {\widetilde{\rme}}
\newcommand{\wtrmE} {\widetilde{\rmE}}
\newcommand{\wtbe} {\widetilde{\be}}
\newcommand{\wtbE} {\widetilde{\bE}}
\newcommand{\whe} {\widehat{e}}
\newcommand{\whE} {\widehat{E}}
\newcommand{\whrme} {\widehat{\rme}}
\newcommand{\whrmE} {\widehat{\rmE}}
\newcommand{\whbe} {\widehat{\be}}
\newcommand{\whbE} {\widehat{\bE}}
\newcommand{\whcE} {\widehat{\cE}}
\newcommand{\whtnsrE} {\widehat{\tnsrE}}
\newcommand{\F} {\mathbb{F}}
\newcommand{\rmf} {\mathrm{f}}
\newcommand{\rmF} {\mathrm{F}}
\newcommand{\bff} {\mathbf{f}}
\newcommand{\bF} {\mathbf{F}}
\newcommand{\cF} {\mathcal{F}}
\newcommand{\bcF} {\boldsymbol{\cF}}
\newcommand{\tnsrF} {\underline{\bF}}
\newcommand{\wtf} {\widetilde{f}}
\newcommand{\wtF} {\widetilde{F}}
\newcommand{\wtrmf} {\widetilde{\rmf}}
\newcommand{\wtrmF} {\widetilde{\rmF}}
\newcommand{\wtbf} {\widetilde{\bf}}
\newcommand{\wtbF} {\widetilde{\bF}}
\newcommand{\whf} {\widehat{f}}
\newcommand{\whF} {\widehat{F}}
\newcommand{\whrmf} {\widehat{\rmf}}
\newcommand{\whrmF} {\widehat{\rmF}}
\newcommand{\whbf} {\widehat{\bf}}
\newcommand{\whbF} {\widehat{\bF}}
\newcommand{\whcF} {\widehat{\cF}}
\newcommand{\whtnsrF} {\widehat{\tnsrF}}
\newcommand{\G} {\mathbb{G}}
\newcommand{\rmg} {\mathrm{g}}
\newcommand{\rmG} {\mathrm{G}}
\newcommand{\bg} {\mathbf{g}}
\newcommand{\bG} {\mathbf{G}}
\newcommand{\cG} {\mathcal{G}}
\newcommand{\bcG} {\boldsymbol{\cG}}
\newcommand{\tnsrG} {\underline{\bG}}
\newcommand{\wtg} {\widetilde{g}}
\newcommand{\wtG} {\widetilde{G}}
\newcommand{\wtrmg} {\widetilde{\rmg}}
\newcommand{\wtrmG} {\widetilde{\rmG}}
\newcommand{\wtbg} {\widetilde{\bg}}
\newcommand{\wtbG} {\widetilde{\bG}}
\newcommand{\whg} {\widehat{g}}
\newcommand{\whG} {\widehat{G}}
\newcommand{\whrmg} {\widehat{\rmg}}
\newcommand{\whrmG} {\widehat{\rmG}}
\newcommand{\whbg} {\widehat{\bg}}
\newcommand{\whbG} {\widehat{\bG}}
\newcommand{\whcG} {\widehat{\cG}}
\newcommand{\whtnsrG} {\widehat{\tnsrG}}
\newcommand{\bbH} {\mathbb{H}}
\newcommand{\rmh} {\mathrm{h}}
\newcommand{\rmH} {\mathrm{H}}
\newcommand{\bh} {\mathbf{h}}
\newcommand{\bH} {\mathbf{H}}
\newcommand{\cH} {\mathcal{H}}
\newcommand{\bcH} {\boldsymbol{\cH}}
\newcommand{\tnsrH} {\underline{\bH}}
\newcommand{\wth} {\widetilde{h}}
\newcommand{\wtH} {\widetilde{H}}
\newcommand{\wtrmh} {\widetilde{\rmh}}
\newcommand{\wtrmH} {\widetilde{\rmH}}
\newcommand{\wtbh} {\widetilde{\bh}}
\newcommand{\wtbH} {\widetilde{\bH}}
\newcommand{\whh} {\widehat{h}}
\newcommand{\whH} {\widehat{H}}
\newcommand{\whrmh} {\widehat{\rmh}}
\newcommand{\whrmH} {\widehat{\rmH}}
\newcommand{\whbh} {\widehat{\bh}}
\newcommand{\whbH} {\widehat{\bH}}
\newcommand{\whcH} {\widehat{\cH}}
\newcommand{\whtnsrH} {\widehat{\tnsrH}}
\newcommand{\I} {\mathbb{I}}
\newcommand{\rmi} {\mathrm{i}}
\newcommand{\rmI} {\mathrm{I}}
\newcommand{\bi} {\mathbf{i}}
\newcommand{\bI} {\mathbf{I}}
\newcommand{\cI} {\mathcal{I}}
\newcommand{\bcI} {\boldsymbol{\cI}}
\newcommand{\tnsrI} {\underline{\bI}}
\newcommand{\wti} {\widetilde{i}}
\newcommand{\wtI} {\widetilde{I}}
\newcommand{\wtrmi} {\widetilde{\rmi}}
\newcommand{\wtrmI} {\widetilde{\rmI}}
\newcommand{\wtbi} {\widetilde{\bi}}
\newcommand{\wtbI} {\widetilde{\bI}}
\newcommand{\whi} {\widehat{i}}
\newcommand{\whI} {\widehat{I}}
\newcommand{\whrmi} {\widehat{\rmi}}
\newcommand{\whrmI} {\widehat{\rmI}}
\newcommand{\whbi} {\widehat{\bi}}
\newcommand{\whbI} {\widehat{\bI}}
\newcommand{\whcI} {\widehat{\cI}}
\newcommand{\whtnsrI} {\widehat{\tnsrI}}
\newcommand{\J} {\mathbb{J}}
\newcommand{\rmj} {\mathrm{j}}
\newcommand{\rmJ} {\mathrm{J}}
\newcommand{\bj} {\mathbf{j}}
\newcommand{\bJ} {\mathbf{J}}
\newcommand{\cJ} {\mathcal{J}}
\newcommand{\bcJ} {\boldsymbol{\cJ}}
\newcommand{\tnsrJ} {\underline{\bJ}}
\newcommand{\wtj} {\widetilde{j}}
\newcommand{\wtJ} {\widetilde{J}}
\newcommand{\wtrmj} {\widetilde{\rmj}}
\newcommand{\wtrmJ} {\widetilde{\rmJ}}
\newcommand{\wtbj} {\widetilde{\bj}}
\newcommand{\wtbJ} {\widetilde{\bJ}}
\newcommand{\whj} {\widehat{j}}
\newcommand{\whJ} {\widehat{J}}
\newcommand{\whrmj} {\widehat{\rmj}}
\newcommand{\whrmJ} {\widehat{\rmJ}}
\newcommand{\whbj} {\widehat{\bj}}
\newcommand{\whbJ} {\widehat{\bJ}}
\newcommand{\whcJ} {\widehat{\cJ}}
\newcommand{\whtnsrJ} {\widehat{\tnsrJ}}
\newcommand{\K} {\mathbb{K}}
\newcommand{\rmk} {\mathrm{k}}
\newcommand{\rmK} {\mathrm{K}}
\newcommand{\bk} {\mathbf{k}}
\newcommand{\bK} {\mathbf{K}}
\newcommand{\cK} {\mathcal{K}}
\newcommand{\bcK} {\boldsymbol{\cK}}
\newcommand{\tnsrK} {\underline{\bK}}
\newcommand{\wtk} {\widetilde{k}}
\newcommand{\wtK} {\widetilde{K}}
\newcommand{\wtrmk} {\widetilde{\rmk}}
\newcommand{\wtrmK} {\widetilde{\rmK}}
\newcommand{\wtbk} {\widetilde{\bk}}
\newcommand{\wtbK} {\widetilde{\bK}}
\newcommand{\whk} {\widehat{k}}
\newcommand{\whK} {\widehat{K}}
\newcommand{\whrmk} {\widehat{\rmk}}
\newcommand{\whrmK} {\widehat{\rmK}}
\newcommand{\whbk} {\widehat{\bk}}
\newcommand{\whbK} {\widehat{\bK}}
\newcommand{\whcK} {\widehat{\cK}}
\newcommand{\whtnsrK} {\widehat{\tnsrK}}
\newcommand{\bbL} {\mathbb{L}}
\newcommand{\rml} {\mathrm{l}}
\newcommand{\rmL} {\mathrm{L}}
\newcommand{\bl} {\mathbf{l}}
\newcommand{\bL} {\mathbf{L}}
\newcommand{\cL} {\mathcal{L}}
\newcommand{\bcL} {\boldsymbol{\cL}}
\newcommand{\tnsrL} {\underline{\bL}}
\newcommand{\wtl} {\widetilde{l}}
\newcommand{\wtL} {\widetilde{L}}
\newcommand{\wtrml} {\widetilde{\rml}}
\newcommand{\wtrmL} {\widetilde{\rmL}}
\newcommand{\wtbl} {\widetilde{\bl}}
\newcommand{\wtbL} {\widetilde{\bL}}
\newcommand{\whl} {\widehat{l}}
\newcommand{\whL} {\widehat{L}}
\newcommand{\whrml} {\widehat{\rml}}
\newcommand{\whrmL} {\widehat{\rmL}}
\newcommand{\whbl} {\widehat{\bl}}
\newcommand{\whbL} {\widehat{\bL}}
\newcommand{\whcL} {\widehat{\cL}}
\newcommand{\whtnsrL} {\widehat{\tnsrL}}
\newcommand{\M} {\mathbb{M}}
\newcommand{\rmm} {\mathrm{m}}
\newcommand{\rmM} {\mathrm{M}}
\newcommand{\bm} {\mathbf{m}}
\newcommand{\bM} {\mathbf{M}}
\newcommand{\cM} {\mathcal{M}}
\newcommand{\bcM} {\boldsymbol{\cM}}
\newcommand{\tnsrM} {\underline{\bM}}
\newcommand{\wtm} {\widetilde{m}}
\newcommand{\wtM} {\widetilde{M}}
\newcommand{\wtrmm} {\widetilde{\rmm}}
\newcommand{\wtrmM} {\widetilde{\rmM}}
\newcommand{\wtbm} {\widetilde{\bm}}
\newcommand{\wtbM} {\widetilde{\bM}}
\newcommand{\whm} {\widehat{m}}
\newcommand{\whM} {\widehat{M}}
\newcommand{\whrmm} {\widehat{\rmm}}
\newcommand{\whrmM} {\widehat{\rmM}}
\newcommand{\whbm} {\widehat{\bm}}
\newcommand{\whbM} {\widehat{\bM}}
\newcommand{\whcM} {\widehat{\cM}}
\newcommand{\whtnsrM} {\widehat{\tnsrM}}
\newcommand{\N} {\mathbb{N}}
\newcommand{\rmn} {\mathrm{n}}
\newcommand{\rmN} {\mathrm{N}}
\newcommand{\bn} {\mathbf{n}}
\newcommand{\bN} {\mathbf{N}}
\newcommand{\cN} {\mathcal{N}}
\newcommand{\bcN} {\boldsymbol{\cN}}
\newcommand{\tnsrN} {\underline{\bN}}
\newcommand{\wtn} {\widetilde{n}}
\newcommand{\wtN} {\widetilde{N}}
\newcommand{\wtrmn} {\widetilde{\rmn}}
\newcommand{\wtrmN} {\widetilde{\rmN}}
\newcommand{\wtbn} {\widetilde{\bn}}
\newcommand{\wtbN} {\widetilde{\bN}}
\newcommand{\whn} {\widehat{n}}
\newcommand{\whN} {\widehat{N}}
\newcommand{\whrmn} {\widehat{\rmn}}
\newcommand{\whrmN} {\widehat{\rmN}}
\newcommand{\whbn} {\widehat{\bn}}
\newcommand{\whbN} {\widehat{\bN}}
\newcommand{\whcN} {\widehat{\cN}}
\newcommand{\whtnsrN} {\widehat{\tnsrN}}
\newcommand{\bbO} {\mathbb{O}}
\newcommand{\rmo} {\mathrm{o}}
\newcommand{\rmO} {\mathrm{O}}
\newcommand{\bo} {\mathbf{o}}
\newcommand{\bO} {\mathbf{O}}
\newcommand{\cO} {\mathcal{O}}
\newcommand{\bcO} {\boldsymbol{\cO}}
\newcommand{\tnsrO} {\underline{\bO}}
\newcommand{\wto} {\widetilde{o}}
\newcommand{\wtO} {\widetilde{O}}
\newcommand{\wtrmo} {\widetilde{\rmo}}
\newcommand{\wtrmO} {\widetilde{\rmO}}
\newcommand{\wtbo} {\widetilde{\bo}}
\newcommand{\wtbO} {\widetilde{\bO}}
\newcommand{\who} {\widehat{o}}
\newcommand{\whO} {\widehat{O}}
\newcommand{\whrmo} {\widehat{\rmo}}
\newcommand{\whrmO} {\widehat{\rmO}}
\newcommand{\whbo} {\widehat{\bo}}
\newcommand{\whbO} {\widehat{\bO}}
\newcommand{\whcO} {\widehat{\cO}}
\newcommand{\whtnsrO} {\widehat{\tnsrO}}
\newcommand{\bbP} {\mathbb{P}}
\newcommand{\rmp} {\mathrm{p}}
\newcommand{\rmP} {\mathrm{P}}
\newcommand{\bp} {\mathbf{p}}
\newcommand{\bP} {\mathbf{P}}
\newcommand{\cP} {\mathcal{P}}
\newcommand{\bcP} {\boldsymbol{\cP}}
\newcommand{\tnsrP} {\underline{\bP}}
\newcommand{\wtp} {\widetilde{p}}
\newcommand{\wtP} {\widetilde{P}}
\newcommand{\wtrmp} {\widetilde{\rmp}}
\newcommand{\wtrmP} {\widetilde{\rmP}}
\newcommand{\wtbp} {\widetilde{\bp}}
\newcommand{\wtbP} {\widetilde{\bP}}
\newcommand{\whp} {\widehat{p}}
\newcommand{\whP} {\widehat{P}}
\newcommand{\whrmp} {\widehat{\rmp}}
\newcommand{\whrmP} {\widehat{\rmP}}
\newcommand{\whbp} {\widehat{\bp}}
\newcommand{\whbP} {\widehat{\bP}}
\newcommand{\whcP} {\widehat{\cP}}
\newcommand{\whtnsrP} {\widehat{\tnsrP}}
\newcommand{\Q} {\mathbb{Q}}
\newcommand{\rmq} {\mathrm{q}}
\newcommand{\rmQ} {\mathrm{Q}}
\newcommand{\bq} {\mathbf{q}}
\newcommand{\bQ} {\mathbf{Q}}
\newcommand{\cQ} {\mathcal{Q}}
\newcommand{\bcQ} {\boldsymbol{\cQ}}
\newcommand{\tnsrQ} {\underline{\bQ}}
\newcommand{\wtq} {\widetilde{q}}
\newcommand{\wtQ} {\widetilde{Q}}
\newcommand{\wtrmq} {\widetilde{\rmq}}
\newcommand{\wtrmQ} {\widetilde{\rmQ}}
\newcommand{\wtbq} {\widetilde{\bq}}
\newcommand{\wtbQ} {\widetilde{\bQ}}
\newcommand{\whq} {\widehat{q}}
\newcommand{\whQ} {\widehat{Q}}
\newcommand{\whrmq} {\widehat{\rmq}}
\newcommand{\whrmQ} {\widehat{\rmQ}}
\newcommand{\whbq} {\widehat{\bq}}
\newcommand{\whbQ} {\widehat{\bQ}}
\newcommand{\whcQ} {\widehat{\cQ}}
\newcommand{\whtnsrQ} {\widehat{\tnsrQ}}
\newcommand{\R} {\mathbb{R}}
\newcommand{\rmr} {\mathrm{r}}
\newcommand{\rmR} {\mathrm{R}}
\newcommand{\br} {\mathbf{r}}
\newcommand{\bR} {\mathbf{R}}
\newcommand{\cR} {\mathcal{R}}
\newcommand{\bcR} {\boldsymbol{\cR}}
\newcommand{\tnsrR} {\underline{\bR}}
\newcommand{\wtr} {\widetilde{r}}
\newcommand{\wtR} {\widetilde{R}}
\newcommand{\wtrmr} {\widetilde{\rmr}}
\newcommand{\wtrmR} {\widetilde{\rmR}}
\newcommand{\wtbr} {\widetilde{\br}}
\newcommand{\wtbR} {\widetilde{\bR}}
\newcommand{\whr} {\widehat{r}}
\newcommand{\whR} {\widehat{R}}
\newcommand{\whrmr} {\widehat{\rmr}}
\newcommand{\whrmR} {\widehat{\rmR}}
\newcommand{\whbr} {\widehat{\br}}
\newcommand{\whbR} {\widehat{\bR}}
\newcommand{\whcR} {\widehat{\cR}}
\newcommand{\whtnsrR} {\widehat{\tnsrR}}
\newcommand{\bbS} {\mathbb{S}}
\newcommand{\rms} {\mathrm{s}}
\newcommand{\rmS} {\mathrm{S}}
\newcommand{\bs} {\mathbf{s}}
\newcommand{\bS} {\mathbf{S}}
\newcommand{\cS} {\mathcal{S}}
\newcommand{\bcS} {\boldsymbol{\cS}}
\newcommand{\tnsrS} {\underline{\bS}}
\newcommand{\wts} {\widetilde{s}}
\newcommand{\wtS} {\widetilde{S}}
\newcommand{\wtrms} {\widetilde{\rms}}
\newcommand{\wtrmS} {\widetilde{\rmS}}
\newcommand{\wtbs} {\widetilde{\bs}}
\newcommand{\wtbS} {\widetilde{\bS}}
\newcommand{\whs} {\widehat{s}}
\newcommand{\whS} {\widehat{S}}
\newcommand{\whrms} {\widehat{\rms}}
\newcommand{\whrmS} {\widehat{\rmS}}
\newcommand{\whbs} {\widehat{\bs}}
\newcommand{\whbS} {\widehat{\bS}}
\newcommand{\whcS} {\widehat{\cS}}
\newcommand{\whtnsrS} {\widehat{\tnsrS}}
\newcommand{\T} {\mathbb{T}}
\newcommand{\rmt} {\mathrm{t}}
\newcommand{\rmT} {\mathrm{T}}
\newcommand{\bt} {\mathbf{t}}
\newcommand{\bT} {\mathbf{T}}
\newcommand{\cT} {\mathcal{T}}
\newcommand{\bcT} {\boldsymbol{\cT}}
\newcommand{\tnsrT} {\underline{\bT}}
\newcommand{\wtt} {\widetilde{t}}
\newcommand{\wtT} {\widetilde{T}}
\newcommand{\wtrmt} {\widetilde{\rmt}}
\newcommand{\wtrmT} {\widetilde{\rmT}}
\newcommand{\wtbt} {\widetilde{\bt}}
\newcommand{\wtbT} {\widetilde{\bT}}
\newcommand{\wht} {\widehat{t}}
\newcommand{\whT} {\widehat{T}}
\newcommand{\whrmt} {\widehat{\rmt}}
\newcommand{\whrmT} {\widehat{\rmT}}
\newcommand{\whbt} {\widehat{\bt}}
\newcommand{\whbT} {\widehat{\bT}}
\newcommand{\whcT} {\widehat{\cT}}
\newcommand{\whtnsrT} {\widehat{\tnsrT}}
\newcommand{\U} {\mathbb{U}}
\newcommand{\rmu} {\mathrm{u}}
\newcommand{\rmU} {\mathrm{U}}
\newcommand{\bu} {\mathbf{u}}
\newcommand{\bU} {\mathbf{U}}
\newcommand{\cU} {\mathcal{U}}
\newcommand{\bcU} {\boldsymbol{\cU}}
\newcommand{\tnsrU} {\underline{\bU}}
\newcommand{\wtu} {\widetilde{u}}
\newcommand{\wtU} {\widetilde{U}}
\newcommand{\wtrmu} {\widetilde{\rmu}}
\newcommand{\wtrmU} {\widetilde{\rmU}}
\newcommand{\wtbu} {\widetilde{\bu}}
\newcommand{\wtbU} {\widetilde{\bU}}
\newcommand{\whu} {\widehat{u}}
\newcommand{\whU} {\widehat{U}}
\newcommand{\whrmu} {\widehat{\rmu}}
\newcommand{\whrmU} {\widehat{\rmU}}
\newcommand{\whbu} {\widehat{\bu}}
\newcommand{\whbU} {\widehat{\bU}}
\newcommand{\whcU} {\widehat{\cU}}
\newcommand{\whtnsrU} {\widehat{\tnsrU}}
\newcommand{\V} {\mathbb{V}}
\newcommand{\rmv} {\mathrm{v}}
\newcommand{\rmV} {\mathrm{V}}
\newcommand{\bv} {\mathbf{v}}
\newcommand{\bV} {\mathbf{V}}
\newcommand{\cV} {\mathcal{V}}
\newcommand{\bcV} {\boldsymbol{\cV}}
\newcommand{\tnsrV} {\underline{\bV}}
\newcommand{\wtv} {\widetilde{v}}
\newcommand{\wtV} {\widetilde{V}}
\newcommand{\wtrmv} {\widetilde{\rmv}}
\newcommand{\wtrmV} {\widetilde{\rmV}}
\newcommand{\wtbv} {\widetilde{\bv}}
\newcommand{\wtbV} {\widetilde{\bV}}
\newcommand{\whv} {\widehat{v}}
\newcommand{\whV} {\widehat{V}}
\newcommand{\whrmv} {\widehat{\rmv}}
\newcommand{\whrmV} {\widehat{\rmV}}
\newcommand{\whbv} {\widehat{\bv}}
\newcommand{\whbV} {\widehat{\bV}}
\newcommand{\whcV} {\widehat{\cV}}
\newcommand{\whtnsrV} {\widehat{\tnsrV}}
\newcommand{\W} {\mathbb{W}}
\newcommand{\rmw} {\mathrm{w}}
\newcommand{\rmW} {\mathrm{W}}
\newcommand{\bw} {\mathbf{w}}
\newcommand{\bW} {\mathbf{W}}
\newcommand{\cW} {\mathcal{W}}
\newcommand{\bcW} {\boldsymbol{\cW}}
\newcommand{\tnsrW} {\underline{\bW}}
\newcommand{\wtw} {\widetilde{w}}
\newcommand{\wtW} {\widetilde{W}}
\newcommand{\wtrmw} {\widetilde{\rmw}}
\newcommand{\wtrmW} {\widetilde{\rmW}}
\newcommand{\wtbw} {\widetilde{\bw}}
\newcommand{\wtbW} {\widetilde{\bW}}
\newcommand{\whw} {\widehat{w}}
\newcommand{\whW} {\widehat{W}}
\newcommand{\whrmw} {\widehat{\rmw}}
\newcommand{\whrmW} {\widehat{\rmW}}
\newcommand{\whbw} {\widehat{\bw}}
\newcommand{\whbW} {\widehat{\bW}}
\newcommand{\whcW} {\widehat{\cW}}
\newcommand{\whtnsrW} {\widehat{\tnsrW}}
\newcommand{\X} {\mathbb{X}}
\newcommand{\rmx} {\mathrm{x}}
\newcommand{\rmX} {\mathrm{X}}
\newcommand{\bx} {\mathbf{x}}
\newcommand{\bX} {\mathbf{X}}
\newcommand{\cX} {\mathcal{X}}
\newcommand{\bcX} {\boldsymbol{\cX}}
\newcommand{\tnsrX} {\underline{\bX}}
\newcommand{\wtx} {\widetilde{x}}
\newcommand{\wtX} {\widetilde{X}}
\newcommand{\wtrmx} {\widetilde{\rmx}}
\newcommand{\wtrmX} {\widetilde{\rmX}}
\newcommand{\wtbx} {\widetilde{\bx}}
\newcommand{\wtbX} {\widetilde{\bX}}
\newcommand{\whx} {\widehat{x}}
\newcommand{\whX} {\widehat{X}}
\newcommand{\whrmx} {\widehat{\rmx}}
\newcommand{\whrmX} {\widehat{\rmX}}
\newcommand{\whbx} {\widehat{\bx}}
\newcommand{\whbX} {\widehat{\bX}}
\newcommand{\whcX} {\widehat{\cX}}
\newcommand{\whtnsrX} {\widehat{\tnsrX}}
\newcommand{\Y} {\mathbb{Y}}
\newcommand{\rmy} {\mathrm{y}}
\newcommand{\rmY} {\mathrm{Y}}
\newcommand{\by} {\mathbf{y}}
\newcommand{\bY} {\mathbf{Y}}
\newcommand{\cY} {\mathcal{Y}}
\newcommand{\bcY} {\boldsymbol{\cY}}
\newcommand{\tnsrY} {\underline{\bY}}
\newcommand{\wty} {\widetilde{y}}
\newcommand{\wtY} {\widetilde{Y}}
\newcommand{\wtrmy} {\widetilde{\rmy}}
\newcommand{\wtrmY} {\widetilde{\rmY}}
\newcommand{\wtby} {\widetilde{\by}}
\newcommand{\wtbY} {\widetilde{\bY}}
\newcommand{\why} {\widehat{y}}
\newcommand{\whY} {\widehat{Y}}
\newcommand{\whrmy} {\widehat{\rmy}}
\newcommand{\whrmY} {\widehat{\rmY}}
\newcommand{\whby} {\widehat{\by}}
\newcommand{\whbY} {\widehat{\bY}}
\newcommand{\whcY} {\widehat{\cY}}
\newcommand{\whtnsrY} {\widehat{\tnsrY}}
\newcommand{\Z} {\mathbb{Z}}
\newcommand{\rmz} {\mathrm{z}}
\newcommand{\rmZ} {\mathrm{Z}}
\newcommand{\bz} {\mathbf{z}}
\newcommand{\bZ} {\mathbf{Z}}
\newcommand{\cZ} {\mathcal{Z}}
\newcommand{\bcZ} {\boldsymbol{\cZ}}
\newcommand{\tnsrZ} {\underline{\bZ}}
\newcommand{\wtz} {\widetilde{z}}
\newcommand{\wtZ} {\widetilde{Z}}
\newcommand{\wtrmz} {\widetilde{\rmz}}
\newcommand{\wtrmZ} {\widetilde{\rmZ}}
\newcommand{\wtbz} {\widetilde{\bz}}
\newcommand{\wtbZ} {\widetilde{\bZ}}
\newcommand{\whz} {\widehat{z}}
\newcommand{\whZ} {\widehat{Z}}
\newcommand{\whrmz} {\widehat{\rmz}}
\newcommand{\whrmZ} {\widehat{\rmZ}}
\newcommand{\whbz} {\widehat{\bz}}
\newcommand{\whbZ} {\widehat{\bZ}}
\newcommand{\whcZ} {\widehat{\cZ}}
\newcommand{\whtnsrZ} {\widehat{\tnsrZ}}
\newcommand{\balpha} {\boldsymbol{\alpha}}
\newcommand{\wtalpha} {\widetilde{\alpha}}
\newcommand{\whalpha} {\widehat{\alpha}}
\newcommand{\wtbalpha} {\widetilde{\balpha}}
\newcommand{\whbalpha} {\widehat{\balpha}}
\newcommand{\bbeta} {\boldsymbol{\beta}}
\newcommand{\wtbeta} {\widetilde{\beta}}
\newcommand{\whbeta} {\widehat{\beta}}
\newcommand{\wtbbeta} {\widetilde{\bbeta}}
\newcommand{\whbbeta} {\widehat{\bbeta}}
\newcommand{\bgamma} {\boldsymbol{\gamma}}
\newcommand{\wtgamma} {\widetilde{\gamma}}
\newcommand{\whgamma} {\widehat{\gamma}}
\newcommand{\wtbgamma} {\widetilde{\bgamma}}
\newcommand{\whbgamma} {\widehat{\bgamma}}
\newcommand{\bdelta} {\boldsymbol{\delta}}
\newcommand{\wtdelta} {\widetilde{\delta}}
\newcommand{\whdelta} {\widehat{\delta}}
\newcommand{\wtbdelta} {\widetilde{\bdelta}}
\newcommand{\whbdelta} {\widehat{\bdelta}}
\newcommand{\bepsilon} {\boldsymbol{\epsilon}}
\newcommand{\wtepsilon} {\widetilde{\epsilon}}
\newcommand{\whepsilon} {\widehat{\epsilon}}
\newcommand{\wtbepsilon}{\widetilde{\bepsilon}}
\newcommand{\whbepsilon}{\widehat{\bepsilon}}
\newcommand{\veps} {\varepsilon}
\newcommand{\bveps} {\boldsymbol{\veps}}
\newcommand{\wtveps} {\widetilde{\veps}}
\newcommand{\whveps} {\widehat{\veps}}
\newcommand{\wtbveps} {\widetilde{\bveps}}
\newcommand{\whbveps} {\widehat{\bveps}}
\newcommand{\bEta} {\boldsymbol{\eta}}
\newcommand{\wteta} {\widetilde{\eta}}
\newcommand{\wheta} {\widehat{\eta}}
\newcommand{\wtbEta} {\widetilde{\bEta}}
\newcommand{\whbEta} {\widehat{\bEta}}
\newcommand{\btheta} {\boldsymbol{\theta}}
\newcommand{\wttheta} {\widetilde{\theta}}
\newcommand{\whtheta} {\widehat{\theta}}
\newcommand{\wtbtheta} {\widetilde{\btheta}}
\newcommand{\whbtheta} {\widehat{\btheta}}
\newcommand{\bvtheta} {\boldsymbol{\vartheta}}
\newcommand{\wtvtheta} {\widetilde{\vartheta}}
\newcommand{\whvtheta} {\widehat{\vartheta}}
\newcommand{\wtbvtheta} {\widetilde{\bvtheta}}
\newcommand{\whbvtheta} {\widehat{\bvtheta}}
\newcommand{\biota} {\boldsymbol{\iota}}
\newcommand{\wtiota} {\widetilde{\iota}}
\newcommand{\whiota} {\widehat{\iota}}
\newcommand{\wtbiota} {\widetilde{\biota}}
\newcommand{\whbiota} {\widehat{\biota}}
\newcommand{\bkappa} {\boldsymbol{\kappa}}
\newcommand{\wtkappa} {\widetilde{\kappa}}
\newcommand{\whkappa} {\widehat{\kappa}}
\newcommand{\wtbkappa} {\widetilde{\bkappa}}
\newcommand{\whbkappa} {\widehat{\bkappa}}
\newcommand{\blambda} {\boldsymbol{\lambda}}
\newcommand{\wtlambda} {\widetilde{\lambda}}
\newcommand{\whlambda} {\widehat{\lambda}}
\newcommand{\wtblambda} {\widetilde{\blambda}}
\newcommand{\whblambda} {\widehat{\blambda}}
\newcommand{\bmu} {\boldsymbol{\mu}}
\newcommand{\wtmu} {\widetilde{\mu}}
\newcommand{\whmu} {\widehat{\mu}}
\newcommand{\wtbmu} {\widetilde{\bmu}}
\newcommand{\whbmu} {\widehat{\bmu}}
\newcommand{\bnu} {\boldsymbol{\nu}}
\newcommand{\wtnu} {\widetilde{\nu}}
\newcommand{\whnu} {\widehat{\nu}}
\newcommand{\wtbnu} {\widetilde{\bnu}}
\newcommand{\whbnu} {\widehat{\bnu}}
\newcommand{\bxi} {\boldsymbol{\xi}}
\newcommand{\wtxi} {\widetilde{\xi}}
\newcommand{\whxi} {\widehat{\xi}}
\newcommand{\wtbxi} {\widetilde{\bxi}}
\newcommand{\whbxi} {\widehat{\bxi}}
\newcommand{\bpi} {\boldsymbol{\pi}}
\newcommand{\wtpi} {\widetilde{\pi}}
\newcommand{\whpi} {\widehat{\pi}}
\newcommand{\wtbpi} {\widetilde{\bpi}}
\newcommand{\whbpi} {\widehat{\bpi}}
\newcommand{\bvpi} {\boldsymbol{\varpi}}
\newcommand{\wtvpi} {\widetilde{\varpi}}
\newcommand{\whvpi} {\widehat{\varpi}}
\newcommand{\wtbvpi} {\widetilde{\bvpi}}
\newcommand{\whbvpi} {\widehat{\bvpi}}
\newcommand{\brho} {\boldsymbol{\rho}}
\newcommand{\wtrho} {\widetilde{\rho}}
\newcommand{\whrho} {\widehat{\rho}}
\newcommand{\wtbrho} {\widetilde{\brho}}
\newcommand{\whbrho} {\widehat{\brho}}
\newcommand{\bvrho} {\boldsymbol{\varrho}}
\newcommand{\wtvrho} {\widetilde{\varrho}}
\newcommand{\whvrho} {\widehat{\varrho}}
\newcommand{\wtbvrho} {\widetilde{\bvrho}}
\newcommand{\whbvrho} {\widehat{\bvrho}}
\newcommand{\bsigma} {\boldsymbol{\sigma}}
\newcommand{\wtsigma} {\widetilde{\sigma}}
\newcommand{\whsigma} {\widehat{\sigma}}
\newcommand{\wtbsigma} {\widetilde{\bsigma}}
\newcommand{\whbsigma} {\widehat{\bsigma}}
\newcommand{\bvsigma} {\boldsymbol{\varsigma}}
\newcommand{\wtvsigma} {\widetilde{\varsigma}}
\newcommand{\whvsigma} {\widehat{\varsigma}}
\newcommand{\wtbvsigma} {\widetilde{\bvsigma}}
\newcommand{\whbvsigma} {\widehat{\bvsigma}}
\newcommand{\btau} {\boldsymbol{\tau}}
\newcommand{\wttau} {\widetilde{\tau}}
\newcommand{\whtau} {\widehat{\tau}}
\newcommand{\wtbtau} {\widetilde{\btau}}
\newcommand{\whbtau} {\widehat{\btau}}
\newcommand{\bupsilon} {\boldsymbol{\upsilon}}
\newcommand{\wtupsilon} {\widetilde{\upsilon}}
\newcommand{\whupsilon} {\widehat{\upsilon}}
\newcommand{\wtbupsilon}{\widetilde{\bupsilon}}
\newcommand{\whbupsilon}{\widehat{\bupsilon}}
\newcommand{\bzeta} {\boldsymbol{\zeta}}
\newcommand{\wtzeta} {\widetilde{\zeta}}
\newcommand{\whzeta} {\widehat{\zeta}}
\newcommand{\wtbzeta}{\widetilde{\bzeta}}
\newcommand{\whbzeta}{\widehat{\bzeta}}
\newcommand{\bphi} {\boldsymbol{\phi}}
\newcommand{\wtphi} {\widetilde{\phi}}
\newcommand{\whphi} {\widehat{\phi}}
\newcommand{\wtbphi} {\widetilde{\bphi}}
\newcommand{\whbphi} {\widehat{\bphi}}
\newcommand{\bvphi} {\boldsymbol{\varphi}}
\newcommand{\wtvphi} {\widetilde{\varphi}}
\newcommand{\whvphi} {\widehat{\varphi}}
\newcommand{\wtbvphi} {\widetilde{\bvphi}}
\newcommand{\whbvphi} {\widehat{\bvphi}}
\newcommand{\bchi} {\boldsymbol{\chi}}
\newcommand{\wtchi} {\widetilde{\chi}}
\newcommand{\whchi} {\widehat{\chi}}
\newcommand{\wtbchi} {\widetilde{\bchi}}
\newcommand{\whbchi} {\widehat{\bchi}}
\newcommand{\bpsi} {\boldsymbol{\psi}}
\newcommand{\wtpsi} {\widetilde{\psi}}
\newcommand{\whpsi} {\widehat{\psi}}
\newcommand{\wtbpsi} {\widetilde{\bpsi}}
\newcommand{\whbpsi} {\widehat{\bpsi}}
\newcommand{\bomega} {\boldsymbol{\omega}}
\newcommand{\wtomega} {\widetilde{\omega}}
\newcommand{\whomega} {\widehat{\omega}}
\newcommand{\wtbomega} {\widetilde{\bomega}}
\newcommand{\whbomega} {\widehat{\bomega}}
\newcommand{\bGamma} {\boldsymbol{\Gamma}}
\newcommand{\wtGamma} {\widetilde{\Gamma}}
\newcommand{\whGamma} {\widehat{\Gamma}}
\newcommand{\wtbGamma} {\widetilde{\bGamma}}
\newcommand{\whbGamma} {\widehat{\bGamma}}
\newcommand{\bDelta} {\boldsymbol{\Delta}}
\newcommand{\wtDelta} {\widetilde{\Delta}}
\newcommand{\whDelta} {\widehat{\Delta}}
\newcommand{\wtbDelta} {\widetilde{\bDelta}}
\newcommand{\whbDelta} {\widehat{\bDelta}}
\newcommand{\bLambda} {\boldsymbol{\Lambda}}
\newcommand{\wtLambda} {\widetilde{\Lambda}}
\newcommand{\whLambda} {\widehat{\Lambda}}
\newcommand{\wtbLambda} {\widetilde{\bLambda}}
\newcommand{\whbLambda} {\widehat{\bLambda}}
\newcommand{\bXi} {\boldsymbol{\Xi}}
\newcommand{\wtXi} {\widetilde{\Xi}}
\newcommand{\whXi} {\widehat{\Xi}}
\newcommand{\wtbXi} {\widetilde{\bXi}}
\newcommand{\whbXi} {\widehat{\bXi}}
\newcommand{\bPi} {\boldsymbol{\Pi}}
\newcommand{\wtPi} {\widetilde{\Pi}}
\newcommand{\whPi} {\widehat{\Pi}}
\newcommand{\wtbPi} {\widetilde{\bPi}}
\newcommand{\whbPi} {\widehat{\bPi}}
\newcommand{\bSigma} {\boldsymbol{\Sigma}}
\newcommand{\wtSigma} {\widetilde{\Sigma}}
\newcommand{\whSigma} {\widehat{\Sigma}}
\newcommand{\wtbSigma} {\widetilde{\bSigma}}
\newcommand{\whbSigma} {\widehat{\bSigma}}
\newcommand{\bUpsilon} {\boldsymbol{\Upsilon}}
\newcommand{\wtUpsilon} {\widetilde{\Upsilon}}
\newcommand{\whUpsilon} {\widehat{\Upsilon}}
\newcommand{\wtbUpsilon}{\widetilde{\bUpsilon}}
\newcommand{\whbUpsilon}{\widehat{\bUpsilon}}
\newcommand{\bPhi} {\boldsymbol{\Phi}}
\newcommand{\wtPhi} {\widetilde{\Phi}}
\newcommand{\whPhi} {\widehat{\Phi}}
\newcommand{\wtbPhi} {\widetilde{\bPhi}}
\newcommand{\whbPhi} {\widehat{\bPhi}}
\newcommand{\bPsi} {\boldsymbol{\Psi}}
\newcommand{\wtPsi} {\widetilde{\Psi}}
\newcommand{\whPsi} {\widehat{\Psi}}
\newcommand{\wtbPsi} {\widetilde{\bPsi}}
\newcommand{\whbPsi} {\widehat{\bPsi}}
\newcommand{\bOmega} {\boldsymbol{\Omega}}
\newcommand{\wtOmega} {\widetilde{\Omega}}
\newcommand{\whOmega} {\widehat{\Omega}}
\newcommand{\wtbOmega} {\widetilde{\bOmega}}
\newcommand{\whbOmega} {\widehat{\bOmega}}
\newcommand{\bzero} {\mathbf{0}}
\newcommand{\bone} {\mathbf{1}}
\newcommand{\norm}[1]{\left\lVert #1 \right\rVert}
\newcommand{\abs}[1]{\left\lvert#1\right\rvert}
\newcommand{\ceil}[1]{\left \lceil #1 \right\rceil}
\)
In this article, we explore the problem of achieving consensus in an undirected connected graph and explore the conditions of convergence on doubly stochastic weight matrix $\bW$.
Given a set of nodes $\cN = {1,2,\ldots,N}$ in a connected graph $\cG = (\cN,\cE)$, where $\cE = \{(i,j), i \neq j, \text{ i,j are connected}\}$ is a set of edges and each edge is an un-ordered pair. Each node $i$ holds a scalar data point $x_i \in \R$ and $\bx^{(t)} = [ x_1^{(t)},x_2^{(t)},\ldots,x_n^{(t)} ]$ is a vector of node values at time $t$. We are interested in computing the average consensus among nodes i.e. finding $\bx^* = \left(\frac{1}{N} \sum\limits_{i=0}^N x_i \right) \bone$, where $\bone$ is a vector of ones. This is usually achieved by:
$$ \lim_{t \rightarrow \infty} \bx^{(t)} = \bx^* $$
A single iteration is defined by a weight matrix $\bW$ of the graph defined as:
$$ \bx^{(t)} = \bW \bx^{(t-1)} $$
where, the weight matrix $\bW$ has a property ($w_{ij}=0, (i,j) \notin \mathcal{E}$). To ensure that $\bx^{(t)} \rightarrow \bx^*$, we per step convergence as:
- $\bx^{(1)} = \bW \bx^{(0)} $
- $\bx^{(0)}$ is the vector of initial values at nodes.
- $ \bx^{(2)} = \bW \bx^{(1)} $. This can be written as: $ \bx^{(2)} = \bW^2 \bx^{(0)} $
So, after $t$ iterations we can write:
$$ \bx^{(t)} = \bW^t \bx^{(0)} $$
Typically, for average consensus we require:
$$ \lim_{t \rightarrow \infty} \bx^{(t)} = \lim_{t \rightarrow \infty} \bW^t \bx^{(0)} $$ which imply: $$ \lim_{t \rightarrow \infty} \bW^t = \bW^ = \frac{1}{n} \bone \bone^T$$
From this we can conclude the following conditions on $\bW$:
- $\bone$ is a right eigenvector of $\bW^*$ i.e. $\bW^*\bone = \frac{1}{n}\bone\bone^T\bone=\frac{1}{n}\bone n = \bone$. And that $\lambda = 1$ is an eigenvalue of $\bW^*$.
- $\bone$ is also a left eigenvector of $\bW^*$. i.e. $\bone^T \bone\bone^T \frac{1}{n} = n\bone^T\frac{1}{n} = \bone^T$
Since $\bW^*$ is a rank 1 matrix with eigenvalue $\lambda = 1$ and $\bone$ as a corresponding eigenvector implies all other eigenvalues to be $0$ which means for any $\bW$ to converge to $\bW^*$ its first eigenvalue must be $1$ and all other eigenvalues $\abs{\lambda_i} < 1$ for $i=2,3,\ldots, N$.
We can easily see for any $\bW$ to converge to $\bW^*$, it must have a $\bone$ as its eigenvector i.e. $\lim_{t \rightarrow \infty} \bW = \bS \lim_{t \rightarrow \infty} \bDelta^t \bS^{-1} = \bW^*$ where $\bS$ contains the eigenvectors of $\bW$ which after $t$ multiplications should concide with eigenvectors of $\bW^*$ and the only eigenvector that concide is $\bone$. Hence, we can conclude that $\bone$ is an eigenvector of both $\bW$ and $\bW^*$, and therefore, we have established the third condition of convergence:
3. $\bW$ has $\lambda_1 = 1$ and $\abs{\lambda_i}<1$ for $i=2,3,\ldots,N$
Convergence Rate:
Now we have established the third condition of convergence, we can ask what key parameter play’s role in the convergence of $\bW$ to $\bW^*$. For $\bW$ to converge to $\bW^*$ we know that $\abs{\lambda_i(\bW^*)} = 0$ for $i \gt 2$, and $\abs{\lambda_i(\bW)} < 1$ for $i>2$, and $\lambda_1 > \lambda_2 \geq \lambda_3 \ldots \geq \lambda_n$, so $\lambda_2$ of $\bW$ plays a vital role in convergence. Larger $|\lambda_2(\bW)|$ more it takes for $\bW$ to converge. So, we can express this as:
$$ \norm{\bW-\frac{1}{n}\bone\bone^T}_2 $$
where $\norm{\cdot}_2$ represents the spectral norm or maximum singular value. Since, $\bW$ and $\bW^*$ both have a common eigenvalue of $1$, and all other eigenvalues of $\bW^*$ are $0$, we have $\abs{\lambda_2(\bW)} = \norm{\bW-\frac{1}{n} \bone \bone^T}_2 = \norm{\bS}_2 \norm{\bDelta – \bDelta^*}_2 \norm{\bS^{-1}}_2$ as both $\bW$ and $\bW^*$ shares the same eigenbasis $\bS$. $\bDelta^*$ is a diagonal matrix defined as: $diag([1,0,0,\ldots,0])$. Considering only vital role played by $\norm{\bDelta – \bDelta^*}_2$, we can write $\abs{\lambda_2(\bW)} = \norm{\bDelta – \bDelta^*}_2$. If we want to have $\epsilon$ convergence in $t$ iterations then we have:
$$
\begin{align}
&(\abs{\lambda_2(\bW)})^t \leq \epsilon \\
&\text{ Taking log on both sides } \\
&t \log{(|\lambda_2(\bW)|)} \leq \log\epsilon \\
&t \geq \ceil{ \frac{\log \epsilon} {\log{ \left( \abs{\lambda_2 (\bW)} \right) }}}
\end{align}
$$
We have an lower bound on $t$. Hence, we can say that for epsilon convergence of $\bW$ to $\bW^*$, no. of iterations should be minimum of $ \ceil{\frac{\log \epsilon}{\log{(\abs{\lambda_2(\bW)})}}}$.
Error Analysis (Scalar Case)
We now observe how the error behaves when each node has a scalar value. We define the error at time $t$ as:
$$
\begin{align}
\epsilon^{(t)} =& \norm{\bx^{(t)}-\bx^*}_2 \\
=& \norm{\bW^t\bx^{(0)}-\bW^*\bx^{(0)} – \bx^* + \bx^*}_2 \\
=& \norm{ \bW^t \bx^{(0)} – \bW^* \bx^{(0)} – \bW^t \bx^* + \bW^* \bx^*}_2 \\
=& \norm{ (\bW^t-\bW^*) \bx^{(0)} – (\bW^t – \bW^*) \bx^*}_2 \\
=& \norm{(\bW^t-\bW^*)(\bx^{(0)} – \bx^*)}_2 \\
\leq & \norm{\bW^t-\bW^*}_2 \norm{\bx^{(0)} – \bx^{*}}_2 \\
=& \lambda_2^t \norm{\bx^{(0)} – \bx^{*}}_2
\end{align}
$$
where $\lambda_2$ is the second largest eigenvalue of $\bW$ in absolute sense. The error computed here is the mean error (square-root) overall all node values bounded by $\lambda_2^t$ after $t$ iterations.
Error in terms of $t$: We have error at time $t$ upper bounded by:
$$
\begin{align}
&\epsilon^{(t)} \leq \lambda_2^t \norm{\bx^{(0)} – \bx^{}}_2 \\
&\frac{e^{(t)}}{\norm{\bx^{(0)} – \bx^{}}_2} \leq \lambda_2^t \\
&\text{Taking log on both sides } \\
&t \leq \frac{\log{\left(\frac{e^{(t)}}{\norm{\bx^{(0)} – \bx^{}}_2}\right)}}{\log{\lambda_2}}
\end{align}
$$
So, for $\epsilon$ convergence; we have the following upper bound on no. of iterations:
$$ t \leq \frac{\log{\left(\frac{\norm{\bx^{(0)} – \bx^{*}}_2}{\epsilon}\right)}}{|\log{\lambda_2}|} $$
or $t \leq \cO\left(\log\left(\frac{1}{\epsilon}\right)\right)$
Vector Analysis
The above analysis what we did is for scalar case. Like when each node has a scalar value. Now we turn our attention to vector cases to compensate for the rising trend of high-dimension data. Suppose each node $i$ holds a vector of data points $\bx_i \in \R^d$ and we define the matrix of all data points as $\bX = [\bx_1, \bx_2, \ldots , \bx_N] \in \R^{d\times N}$ across all nodes $N$. At time $t$ we define the data matrix as: $\bX^{(t)} = [\bx^{(t)}_1, \bx^{(t)}_2, \ldots , \bx^{(t)}_N] \in \R^{d\times N}$. We further define the average matrix of all $d$ features across all $N$ nodes by $\bX^* = \bX^{(0)} \bW^*$ where each column of $\bX^*$ contains the average vector $\bx^*$ having averaging consensus of $d$ features across $N$ nodes. The update iteration can be written as:
$$ \bX^{(t)} = \bX^{(t-1)}W $$
or
$$ \bX^{(t)} = \bX^{(0)}W^t$$
Error Convergence Analysis
We now move towards how the error behaves as we have multiple features. Let
$$ \bE^{(t)} = \bX^{(t)} – \bX^* $$
The matrix $\bE$ stores the difference between the node values from their averages. We can further analyze:
$$
\begin{align}
\bE^{(t)} =& \bX^{(t)} – \bX^* \\
=& \bX^{(0)} \bW^t – \bX^{(0)}\bW^* \\
=& \bX^{(0)}\bW^t – \bX^{(0)}\bW^* – \bX^* + \bX^* \\
=& \bX^{(0)}\bW^t – \bX^{(0)}\bW^* – \bX^* \bW^t + \bX^* \bW^* \\
=& (\bX^{(0)}-\bX^*) (\bW^t – \bW^*)
\end{align}
$$
As each column of $\bE^{(t)}$ has an error of entries of node $i$ from average $\bx^*$. The target is to bound the norm of the columns of $\bE^{(t)}$. So we use Forbenius norm:
$$
\begin{align}
\norm{\be_i^{(t)}}_2 \leq & \norm{\bE^{(t)}}_F \\
=& \norm{(\bX^{(0)}-\bX^*) (\bW^t – \bW^*)}_F \\
\leq& \norm{\bX^{(0)} – \bX^*}_F \norm{\bW^t-\bW^*}_2 \\
\leq& \lambda_2^t \norm{\bX^{(0)} – \bX^*}_F
\end{align}
$$
where $\lambda_2$ is defined as the second largest eigenvalue of the matrix $\bW$ in absolute sense. So, for a given error per node $i$, we have the following upper bound on no. of iterations:
$$ t \leq \max_i \frac{\log\left( \frac{\norm{\be_i^{(t)}}_2}{\norm{\bX^{(0)} – \bX^*}_F}\right)}{\log(\lambda_2)} $$
We define $\epsilon^{(t)} = \norm{\bE^{(t)}}_F$, this represent the total error accumulated at all nodes at time $t$. Then we have:
$$
\begin{align}
\epsilon^{(t)} =& \norm{\bE^{(t)}}_F \\
=& \norm{(\bX^{(0)}-\bX^*) (\bW^t – \bW^*)}_F \\
\leq& \norm{\bX^{(0)} – \bX^*}_F \norm{\bW^t-\bW^*}_2 \\
\leq& \lambda_2^t \norm{\bX^{(0)} – \bX^*}_F
\end{align}
$$
where $\lambda_2$ is defined as the second largest eigenvalue of the matrix $\bW$ in absolute sense. So, for a given error, we have the following upper bound on no. of iterations:
$$ t \leq \frac{\log\left( \frac{\norm{\bX^{(0)} – \bX^*}_F}{\epsilon}\right)}{|\log(\lambda_2)|} $$
Note: This bound on no. of iterations dictates on how far $\bX^{(0)}$ from $\bX^{*}$ in terms of Forbenius norm given $\epsilon$. This is different than on how many iterations you are required to reach $\bq^*$, which is defined in the following section. Typically, this says that after $t$ communication rounds your initial node values reach within $\epsilon$ neighborhood of the true average.
Recent Comments