tag:blogger.com,1999:blog-38396347173777603402024-03-09T18:45:59.190-08:00謝宗翰的隨筆 If you can’t solve a problem, then there is an easier problem you can solve: find it. -George PolyaC. H. Hsiehhttp://www.blogger.com/profile/18005098064728038131noreply@blogger.comBlogger354125tag:blogger.com,1999:blog-3839634717377760340.post-20142543129660149882023-07-12T07:34:00.008-07:002023-09-07T07:46:11.486-07:00[轉載] PhD Simulator by Mianzhi Wang <p>模擬讀博士的小遊戲 by <a href="https://research.wmz.ninja/" target="_blank">Mianzhi Wang</a> ,個人覺得蠻貼近真實世界的情況,推薦給有興趣的朋朋玩玩看(見以下連結)。</p><p style="text-align: center;"> <a href="https://research.wmz.ninja/projects/phd/index.html?fbclid=IwAR384EpuaxVZP0xfC-0gjUt0sT-v4ghV26AebU3WB0DRcWBeR8Uep_J4_00">PhD Simulator (wmz.ninja)</a></p><br /><br />只要發三篇論文就可以畢業,我想應該不會太難 (?)<br />C. H. Hsiehhttp://www.blogger.com/profile/18005098064728038131noreply@blogger.com0tag:blogger.com,1999:blog-3839634717377760340.post-21606151968048854712022-02-17T23:28:00.027-08:002022-05-15T10:35:06.947-07:00[隨筆] 指導教授的要求與省思<p>這一學期以來,我很幸運陸續有幾位碩士班同學表達有意願想找我當指導教授,我對每一位來訪的同學都表明如果想找我當指導教授的話需要有 (or 致力達成) 以下兩個條件:</p><p></p><ol style="text-align: left;"><li>修習過 高等微積分 (or 數學分析或者等價的課程) </li><li>至少能使用一種程式語言(Matlab, Python, R, C,...)實現各種算法。</li></ol><p></p><p>我對(碩士班)學生的畢業期許是 至少有一篇同儕受審的領域內會議論文投稿。</p><p>我知道上述的要求(特別是條件1)對許多同學而言是極為*沈重*的負擔,因為學生們大多沒有接受過嚴格的數理論證訓練,也並不是每一位都志在學術,大多數同學也許更在乎的是找實習/找工作機會加入業界崗位,更在意的大多都不是碩士論文做了什麼題目,而是能不能準時畢業。我曾經也是學生,我想我大概可以體會這些同學的想法。</p><p>然而,另一方面,我是做*理論*研究的學者,我感興趣的研究領域(<a href="https://en.wikipedia.org/wiki/Stochastic_control" target="_blank">隨機系統</a>與<a href="https://en.wikipedia.org/wiki/Portfolio_optimization" target="_blank">投資組合優化</a>理論)中許許多多的研究確實需要使用各種 數學工具 與 數學論證的手法。領域內的研究工作者需要能大致讀懂領域內相關文獻,並據此發想可能的新研究主題,接著利用各種(數學/優化/統計)工具來解決這些問題。陳述自己的研究成果方法多半是以定義/定理/證明的形式或者 算法/證明/實證模擬結果。最後實證的部分需使用真實資料輔以程式來實現。如果沒有受過一些嚴格論證的訓練與洗禮以及一定的程式撰寫經驗,要達成上述目標幾乎是寸步難行,特別是論證這塊,除了高微這門課之外我實在很難找到更好的替代方案。</p><p>學生們感到(辛苦)困難,老師也感到困難。或許我應該再想想有沒有更好的解決方案?</p><p><br /></p>相關閱讀:<div>彭明輝,2012,<a href="https://mhperng.blogspot.com/2012/05/blog-post_08.html">指導教授的角色與責任</a>,清大彭明輝的部落格</div><div><br /></div><div><br /></div><div><br /><p><br /></p><p><br /></p><p><br /></p></div>C. H. Hsiehhttp://www.blogger.com/profile/18005098064728038131noreply@blogger.com0tag:blogger.com,1999:blog-3839634717377760340.post-79054671763618350312022-01-17T09:17:00.008-08:002022-01-18T05:11:10.579-08:00「轉載」錢本草-張說<div style="text-align: justify;">錢味甘,大熱有毒,偏能駐顏,彩澤流潤,善療饑寒困戹之患,立驗。能利邦國,汙賢達,畏清廉。貪婪者服之,以均平為良,如不均平,則冷熱相激,令人霍亂。其藥采無時,采至非理則傷神。此既流行,能役神靈,通鬼氣。如積而不散,則有水火盜賊之災生;如散而不積,則有饑寒困厄之患至。一積一散謂之道,不以為珍謂之德,取與合宜謂之義,無求非分謂之禮,博施濟眾謂之仁,出不失期謂之信,入不妨己謂之智,以此七術精煉方可。久而服之,令人長壽;若服之非理,則弱誌傷神,切須忌之。</div><div><br /></div>作者:唐 <a href="https://zh.m.wikisource.org/wiki/Author:%E5%BC%B5%E8%AA%AA">張說</a><div><br /></div><div><div><br /></div></div><div><br /></div><br />譯文(編修版)<br /><br />錢,味甜,性熱有毒,卻能預防衰老,駐容養顏。可以治療飢餓寒冷,解決困難,效果明顯。可以有利於國家和百姓,可以污損賢達,只是害怕清廉。貪婪之人服用以不過分為好,如果過度,則冷熱不均,引發霍亂。這味藥,沒有固定的採摘時節,無理採摘的使人精神損傷。如果只積攢不發散,會有水火盜賊等災難。如果只發散不積攢,會有饑寒困頓等禍患。一邊積攢一邊施財可稱為道,不把錢財當作珍寶稱為德,取得給予適宜稱為義,不求非份之財使用正當稱為禮,接濟大眾稱為仁,支出有度歸還有期稱為信,得錢財又不傷自己稱為智,用道,德,仁,義,禮,智,信這七種方法精鍊此藥,才可以長久地服用他。可以使人延年益壽,如果不這麼服用,則會智力減弱精神損傷,這點需要特別避免。<div><br /></div><div><br /></div><div><br /></div>C. H. Hsiehhttp://www.blogger.com/profile/18005098064728038131noreply@blogger.com0tag:blogger.com,1999:blog-3839634717377760340.post-30188399789298692392021-03-23T09:17:00.004-07:002021-03-23T09:18:27.465-07:00[機率論] 兩隨機變數相等表示兩者有相同分布但反之不然<b>Claim: </b>給定機率空間 $(\Omega, \mathcal{F}, P)$,令$X$與$Y$為兩隨機變數。若 $P(X=Y)=1$ 則$X$與$Y$有相同分布,亦即對任意可測集合 $A \in \mathcal{F}$,<div>$$P(X \in A) = P(Y \in A)$$</div><div><br /></div><div><b>Proof: </b>令$A \in \mathcal{F}$,我們觀察<br />$$<br />P(X\in A\cap X\neq Y)\leq P(X\neq Y)=0<br />$$ 故可推得 $P(X\in A\cap X\neq Y)=0$。利用此結果,我們注意到 <br />$$<br />P(X\in A)=P(X\in A\cap X=Y)+\underbrace{P(X\in A\cap X\neq Y)}_{=0}=P(X\in A\cap X=Y)<br />$$
同理我們亦可觀察 $P(Y\in A)=P(Y\in A\cap X=Y)$。注意到若我們可證明 $$P(X\in A\cap X=Y) = P(Y\in A\cap X=Y) \;\;\;\;\; (*)$$則 $$P(X\in A)=P(X\in A\cap X=Y)=P(Y\in A\cap X=Y)=P(Y\in A)$$即為所求。</div><div><br /></div><div>現在我們回頭證明等式$(*)$。我們僅須證明下列事件集合等式關係成立 $$\{X\in A\cap X=Y\} = \{Y\in A\cap X=Y\} $$即可。首先證明 $\{X\in A\cap X=Y\} \subset \{Y\in A\cap X=Y\} $: 令 $\omega \in \{ X \in A\cap X=Y\}$ 即表明 $X(\omega) \in A$ 且 $X(\omega) = Y(\omega)$。 故我們可推得 $Y(\omega) \in A$ 故此,$\omega \in \{Y \in A\cap X=Y\}$。亦即$$\{X\in A\cap X=Y\} \subset \{Y\in A\cap X=Y\} $$ 同理不難證得 $\{X\in A\cap X=Y\} \supset \{Y\in A\cap X=Y\} $。故我們得到 $\{X\in A\cap X=Y\} = \{Y\in A\cap X=Y\} $至此證明完畢。$\square$</div><div><br /></div><div><br /></div><div>上述 Claim 的反面論述並不成立。以下我們給個反例:考慮均勻分布 $X$為隨機變數服從均勻分布 $U[-1,1]$ 現在取另一隨機變數 $Y:=-X$則 $Y$亦為在 $[-1,1]$上均勻分布,亦即 $X$與 $Y$具有同分布。然而</div><div>$$P(X = Y) = 0$$</div><div><br /></div>C. H. Hsiehhttp://www.blogger.com/profile/18005098064728038131noreply@blogger.com1tag:blogger.com,1999:blog-3839634717377760340.post-91514844535764976762021-02-12T08:29:00.004-08:002021-02-12T08:30:18.530-08:00[機率論] 一類含有supremum運算與期望值的不等式問題<p>令 $X,Y$ 為兩隨機變數定義在某機率空間 $(\Omega, \mathcal{B}, P)$ 且 $f: \mathbb{R}^2 \to \mathbb{R}$ 為一連續函數。若對 $X$ 的實現 $X=x$ 而言 (亦即,存在 $\omega \in \Omega$ 使得 $X(\omega) = x$ ),我們顯然有 $$\mathbb{E}[f(x,Y)] \leq \sup_x \mathbb{E}[f(x,Y)]$$試問上述不等式左方若將 $x$ 換回隨機變數 $X$ 時仍然成立?亦即我們想問 $$\mathbb{E}[f(X,Y)] \leq ? \sup_x \mathbb{E}[f(x,Y)]$$</p><p>答案是否定的,我們看以下的反例:</p><p><b><br /></b></p><p><b>Counterexample</b></p><p>考慮隨機變數 $X=Y$ 且 $P(X=1)=P(X=-1) = 1/2$ 且 $f(x,y) := xy$ 則我們可驗證 $$\mathbb{E}[f(X,Y)] = \mathbb{E}[X^2] = 1/2 + 1/2 = 1$$然而如果我們觀察 $$\mathbb{E}[f(1,Y)] = \mathbb{E}[Y] = \mathbb{E}[X] = 0$$ 另外 $$\mathbb{E}[f(-1,Y)] = \mathbb{E}[-Y] = -\mathbb{E}[X] = 0$$ 故 $\sup_x\mathbb{E}[f(x,Y)] = 0$但是 $$\sup_x\mathbb{E}[f(x,Y)] < \mathbb{E}[f(X,Y)]$$</p>C. H. Hsiehhttp://www.blogger.com/profile/18005098064728038131noreply@blogger.com0tag:blogger.com,1999:blog-3839634717377760340.post-12845864923035103762021-02-10T21:50:00.021-08:002021-03-17T01:28:31.754-07:00[機率論] 關於條件期望的一些基本觀念<p>在大學部機率論課程後半大多會介紹到所謂條件機率與條件期望,其中條件期望由於授課時間較接近晚期且觸及之內容較深,初次學習時並不容易掌握。以下我們試圖說明條件期望值本身為一隨機變數並給出一個簡單的例子做配搭。</p><p><br /></p><p><b>條件機率為一隨機變數</b></p><p>令$X,Y$ 為兩隨機變數。假設$X$ 有給定事件 $\{Y=y\}$ 的條件機率分布其中 $y$ 表示隨機變數 $Y$ 所能取到的值。 既然有條件機率分布,則條件期望值存在,我們將其記作 $$\mathbb{E}[X\mid Y=y]$$ 注意到條件期望值與取值 $y$ 相關,故我們可寫 $$\mathbb{E}[X\mid Y=y]:=g(y)$$ 其中 $g(y)$ 表示為 $y$的函數 。依此,若我們把取值 $y$用 $Y$ 代回,則$g(Y)$ 為一<b>隨機變數</b>,記作 $\mathbb{E}[X \mid Y]$。</p><p><br /></p><p><b>重疊期望性質 (Law of Iterated Expectations)</b></p><p>一般期望值與條件期望之間的關係可由 law of iterated expectations (或稱 law of total expectation) 定理刻劃。亦即 $$\mathbb{E}[X] = \mathbb{E}_Y[\mathbb{E}_X[X \mid Y]] $$其中 $\mathbb{E}_Y$表對 $Y$取期望 且 $\mathbb{E}_X$表對 $X$ 取期望。一般而言下標多半不寫出,多簡寫作 $$\mathbb{E}[X] = \mathbb{E}[\mathbb{E}[X \mid Y]] $$</p><p><br /></p><p>以下我們看個具體的例子。讀者按照此例應可看出為何上述條件期望為隨機變數。並練習計算條件期望與使用重疊期望性質。</p><p>=======================</p><p><b>Example: </b>假設有五顆紅球與三顆綠球被放在一袋中,現在我們從中依序取出兩球不放回。令 $Y$ 為第一次取到紅球的計數 ($Y\in \{0,1\}$其中$Y=0$表示第一次沒取到 $Y=1$表示第一次取到),且 $X$ 為第二次取到紅球的計數 ($X \in \{0,1\}$ 其中 $X=0$表示第二次沒取到紅球,$X=1$表示第二次沒取到)。則 $X,Y$皆為(離散)隨機變數。求</p><p>(a) $\mathbb{E}[X \mid Y=0]$ 與 $\mathbb{E}[X \mid Y=1]$ <br />(b) $\mathbb{E}[X \mid Y]$<br />(c) $\mathbb{E}[\mathbb{E}[X \mid Y]]$ 與 $\mathbb{E}[X]$。並驗證此兩者相等。</p><p>========================</p><p><b>Answer: </b>首先注意到 $$Y = \begin{cases} 0 & \text{with probability } \dfrac 3 8, \\[6pt]1 & \text{with probability } \dfrac 5 8. \end{cases}$$ 接著我們依序計算所求:</p><p>(a) 注意到 $$\begin{align}\mathbb{E}[X\mid Y=0] &= \sum_i i P(X=i \mid Y=0) \\&= 1\cdot P(X=1 \mid Y=0) + 0\cdot P(X=0 \mid Y=0) \\&= \dfrac 5 7 + 0 = \dfrac 5 7\end{align}$$ 同理$$\mathbb{E}[X\mid Y=1]= \sum_i i P(X=i \mid Y=1) = P(X=1 \mid Y=1) =\dfrac 4 7$$ 故此</p><p>(b) 由 (a)可知 $\mathbb{E}[X \mid Y] $ 為隨機變數滿足 $$\mathbb{E}[X \mid Y] = \begin{cases} \mathbb{E}[X\mid Y=0]=\dfrac 5 7 & \text{with probability } \dfrac 3 8, \\[6pt]\mathbb{E}[X\mid Y=1]=\dfrac 4 7 & \text{with probability } \dfrac 5 8. \end{cases}$$ </p><p>(c) 一但有了隨機變數 $\mathbb{E}[X \mid Y] $ 的機率分布,由 law of iterated expectation 我們可直接計算 $\mathbb{E}[\mathbb{E}[X\mid Y]]$ 並驗證此確實等同於 $\mathbb{E}[X]$。亦即我們計算 $$\begin{align} \mathbb{E}[\mathbb{E}[X\mid Y]] &= \sum_{i} \mathbb{E}[X\mid Y=i] P(Y=i) \\&= 1 \cdot \mathbb{E}[X \mid Y=1] P(Y=1) + \mathbb{E}[X \mid Y=0] P(Y=0) \\& = \dfrac 5 7 \cdot \dfrac 3 8 + \dfrac 4 7 \cdot \dfrac 5 8 = \dfrac {35} {56}\end{align}$$</p><p>另一方面,我們直接計算 $\mathbb{E}[X]$ :利用期望值的定義如下 $$\begin{align}\mathbb{E}[X] &= \sum_i i P(X=i) \\&=1 \cdot P(X=1) + 0 \cdot P(X=0) \\ & = P(X=1,Y=0) + P(X=1,Y=1) \\ &= P(X=1|Y=0)P(Y=0) + P(X=1|Y=1)P(Y=1) \\&= \dfrac 5 7 \cdot \dfrac 3 8 + \dfrac 4 7 \cdot \dfrac 5 8 = \dfrac {35} {56}\end{align}$$與前述結果一致,至此得證。</p><p><br /></p><p><br /></p><p><br /></p><p><br /></p><p><br /></p><p><br /></p><p><br /></p><p><br /></p><p><br /></p>C. H. Hsiehhttp://www.blogger.com/profile/18005098064728038131noreply@blogger.com0tag:blogger.com,1999:blog-3839634717377760340.post-86586873942105012392020-02-09T11:20:00.000-08:002020-02-09T11:20:27.618-08:00[數學分析] 一類 max/min operator 作用在分式 的等式令函數 $f: \mathbb{N} \to (0,\infty)$,則下列等式成立<br />
$$<br />
\min_{0 \leq k \leq N} \frac{f(k)}{\max_{i\leq k}f(i)} = \min_{0\leq \ell \leq k \leq N} \frac{f(k)}{f(\ell)}<br />
$$<br />
<br />
<b>Proof: </b>令<br />
$$\frac{f(k_0)}{f(\ell_0)} := \min_{0\leq k\leq N}\frac{f(k)}{ \max_{i\leq k} f(i)}<br />
$$ 其中 $\ell_0\leq k_0$ 使得 $\text{min}_{0\leq\ell\leq k\leq N}\frac{f(k)}{f(\ell)}\leq\frac{f(k_0)}{f(\ell_0)}$。<br />
<br />
另一方面,令<br />
$$\frac{f(k_1)}{f(\ell_1)}= \min_{0\leq\ell\leq k\leq N}\frac{f(k)}{f(\ell)}<br />
$$ 且 $\ell_1\leq k_1$,則我們必定有<br />
$$\frac{f(k_0)}{f(\ell_0)}\leq\frac{f(k_1)}{ \max_{i\leq k_1}\;f(i)}\leq\frac{f(k_1)}{f(\ell_1)}$$<br />
由上述結果,我們得到<br />
$$<br />
\frac{f(k_0)}{f(\ell_0)}=\frac{f(k_1)}{f(\ell_1)}<br />
$$ 亦即<br />
$$\min_{0\leq k\leq N}\frac{f(k)}{ \max_{i\leq k} f(i)}= \min_{0\leq\ell\leq k\leq N}\frac{f(k)}{f(\ell)}$$ 至此得證。$\square$C. H. Hsiehhttp://www.blogger.com/profile/18005098064728038131noreply@blogger.com0tag:blogger.com,1999:blog-3839634717377760340.post-25166138005619451232019-12-18T20:55:00.010-08:002021-02-24T05:39:55.619-08:00[隨筆] 博士之路的感謝<i>六十餘年妄學詩,功夫深處獨心知</i><br />
<i>夜來一笑寒燈下,始是金丹換骨時</i><br />
<i><br /></i>
<i>陸游 --- 夜吟</i><br />
<br />
---<br />
昨天 (12/17/2019) 我完成了我的博士論文答辯。我想趁著一切記憶還鮮明的時候 寫寫我的想法與心中的感謝。<br />
<br />
<br />
<b>心境</b><br />
從 2013 到執筆寫下這篇文章的今天,六年多將近七年的留美歲月恍如昨日,當日少年轉眼變成大叔。我猶記剛剛踏上 Madison, Wisconsin 時候的大雪紛飛與零下 20 度的氣溫。我瑟瑟發抖,套上好友送的防寒手套,心中想著即將與剛新婚不久的 太太 順瑩 分離,經濟上與課業上的全新挑戰。這是個用英文點杯咖啡都顯得結巴困難的日子。<br />
<br />
<br />
<br />
<b>關於課業與研究</b><br />
我是在 <a href="https://www.wisc.edu/" target="_blank">UW-Madison</a> <a href="https://www.engr.wisc.edu/department/electrical-computer-engineering/" target="_blank">電機與電腦工程系</a> 攻讀博士,主修 控制系統 輔修 數學。我有幸師從 <a href="https://directory.engr.wisc.edu/ece/Faculty/Barmish_B/" target="_blank">B. Ross Barmish </a>教授,他是 <a href="https://en.wikipedia.org/wiki/Robust_control" target="_blank">強健控制</a> 與 <a href="https://en.wikipedia.org/wiki/Control_system" target="_blank">控制工程</a>在財務應用 的幾位領頭人物之一。<br />
<br />
我主要研究領域是落在 <a href="https://en.wikipedia.org/wiki/Stochastic_process" target="_blank">隨機系統</a> 與 <a href="https://en.wikipedia.org/wiki/Financial_engineering" target="_blank">財務工程</a> 的交集<sup>1</sup>。讀博期間很慶幸在許多師長的幫助之下,順道取得同校的 數學與電機 雙碩士學位,加上我原本在台灣的機械碩士,僥倖集滿了三碩,多了幾根白髮,發了幾篇文章。最開心的大概是我終於可以厚顏自稱自己是 <a href="https://genealogy.math.ndsu.nodak.edu/id.php?id=257222" target="_blank">(應用) 數學家</a>。 彷彿又更接近了一點當年在大學時候的夢想:成為一位 <a href="https://en.wikipedia.org/wiki/Control_theory" target="_blank">控制理論</a> 學者。 讀博過程,除了研究之外,更常時候是在等待論文審核的時光中度過。填補這個等待就是做新的研究。一個挖坑又自己填坑的過程。很多煎熬,很多難關。許許多多的人在這路上幫助過我,或先或後,或直接或間接,難以計數,我由衷謝謝他們。<br />
<br />
<br />
<br />
<b>關於經濟</b><br />
除了幾個特定<a href="https://en.wikipedia.org/wiki/Machine_learning" target="_blank">超熱門領域</a>之外,做理論研究並沒有太多經費。所以我得在 興趣 與 麵包 之間做選擇。我選了前者,也因此開啟了長年教課的日子。我感謝 UW-Madison <a href="https://www.math.wisc.edu/" target="_blank">數學系</a> 與 <a href="https://www.engr.wisc.edu/department/electrical-computer-engineering/" target="_blank">電機系</a> 願意給我機會擔任 助教 或者 講師 職位。我由衷謝謝他們。<br />
<br />
<br />
<br />
<b>關於博士答辯之後與博士頭銜</b><br />
答辯之前與答辯之後並沒有不同,答辯之後並沒有讓我對研究領域的認識就瞬間有了質的飛躍,更多時候是細水長流的累積直到答辯的那一刻。論文答辯 本身 不過是給我一個機會 分享總結 自己過去這些年的一些些研究成果。若要說博士頭銜有什麼作用,大概就是讓我得到了一個奢侈的特權:得到申請 助理教授 職位被拒絕的特權。希望這個特權不用被使用太多次...(註: 作者已接受<a href="https://www.nthu.edu.tw/" target="_blank">國立清華大學</a> <a href="http://www.qf.nthu.edu.tw/" target="_blank">計量財務金融學系</a> 的邀約成為該系2021年新聘助理教授)<br />
<br />
<br />
<br />
<b>關於家人</b><br />
我的太太 順瑩 與台灣的家人們 是我最大的後盾。在我讀博期間,不論在經濟上,情感上都給予我極大的支持。為了我的控制學者夢,她三番兩次放下手邊的工作,來到一個語言不是很通的國家,費心分擔家務,照顧年幼的 我兒 亞諾,在此由衷感謝她的愛與付出。<br />
<br />
<br />
<br />
<b>關於信仰</b><br />
對我而言,人更多是在低處或者痛苦的時候才會想要找到 上帝。我出國前曾經在 <a href="https://1882pcc.webnode.tw/" target="_blank">板橋基督長老教會</a> 分享過一次 <a href="https://ch-hsieh.blogspot.com/2012/10/blog-post.html" target="_blank">約伯記導讀--苦難的根源</a>,這些年的經歷讓我覺得 神 真是幽默無比,這分享根本就是講給我自己聽的。我感謝我所信的這位 神,他讓我知道我雖經過死蔭幽谷,祂仍眷顧 並與我同行。這條博士之路,我想更是一條恩典之路。<br />
<br />
<br />
<br />
宗翰 2019<br />
於 Madison, Wisconsin<br />
<br />
<br />
<sup>1</sup> 關於我的博士論文主題: Contributions to the Theory of Kelly Betting with Applications to Stock Trading: A Control-Theoretic Approach 有興趣的讀者可參考ProQuest<a href="https://search.proquest.com/docview/2338533627?fromopenview=true&pq-origsite=gscholar" target="_blank">連結</a> 或者 個人Dropbox空間<a href="https://www.dropbox.com/s/fphvyel5lu4mmsh/Dissertation_chhsieh_proquest_ver.pdf?dl=0" target="_blank">連結</a><br />
<br />
<br />C. H. Hsiehhttp://www.blogger.com/profile/18005098064728038131noreply@blogger.com6tag:blogger.com,1999:blog-3839634717377760340.post-14985130093281410392019-12-11T01:08:00.004-08:002019-12-12T14:37:05.768-08:00[分享] 板橋教會敬拜讚美團 『決定,回家』 20週年 紀念音樂專輯板橋教會敬拜讚美團 『決定,回家』 20週年 紀念音樂專輯。<br />
<br />
<br />
<iframe allowfullscreen="" frameborder="0" height="270" src="https://www.youtube.com/embed/7u7v768WhJg" width="480"></iframe><br />
<br />
<div class="separator" style="clear: both; text-align: left;">
<br /></div>
<br />
<iframe allowfullscreen="" frameborder="0" height="270" src="https://www.youtube.com/embed/dQ7u3Hy3UkA" width="480"></iframe>
<br />
<br />
<br />
<iframe allowfullscreen="" frameborder="0" height="270" src="https://www.youtube.com/embed/gkvTfZzckWI" width="480"></iframe>
<br />
整張專輯:<br />
<br />
<iframe allowfullscreen="" frameborder="0" height="344" src="https://www.youtube.com/embed/videoseries?list=PLjN_dyKH5A0VjTYsW9nidHUlRHzW1anG0" width="425"></iframe><br />
<br />
謝謝你們。<br />
<br />
<br />C. H. Hsiehhttp://www.blogger.com/profile/18005098064728038131noreply@blogger.com0tag:blogger.com,1999:blog-3839634717377760340.post-81510077413536183312019-12-08T13:52:00.000-08:002019-12-10T12:47:55.078-08:00[凸分析] 凸優化最佳解所成之集合為凸集在凸優化問題中,僅管凸性保證了任意局部最優解 (local minimizer) 就是 全局最優解 (global minimizer),但凸性並沒有保證所考慮的凸優化問題 一定 <b>存在 </b>最優極小解。下面的結果刻劃了凸優化最佳解的性質,常被用來檢驗最佳解的存在性,是個十分有用的結果。<br />
<br />
===========<br />
<b>Theorem: (凸優化最佳解的集合為凸集)</b><br />
令 $S \subseteq \mathbb{R}^n$ 為 凸集合 且 $f: S\to \mathbb{R}$ 為 凸函數。令 $S^*$ 為所有極小點所成之集合亦即<br />
\[<br />
S^* := \{x\in S: f(x) \leq f(y), \forall \; y \in S\; \}<br />
\] 則 $S^*$ 為凸集。<br />
===========<br />
<div>
<br /></div>
<b>Proof</b>: 若 $S^* = \emptyset$ 則上述定理陳述自動成立。若 $S^* \neq \emptyset$,則存在 $x_0 \in S^*$。考慮 level set<br />
\[<br />
S_{\leq f(x_0)} := \{x\in S: f(x) \leq f(x_0)\}<br />
\] 則不難驗證 $S_{\leq f(x_0)} = S^*$。接著由下述 Lemma 可知 $S^*$ 為 convex。至此證明完畢。$\square$<br />
<br />
<br />
===========<br />
<b>Lemma: </b>令 $S \subseteq \mathbb{R}^n$為凸集,且 $f:S \to \mathbb{R}$ 為凸函數。則對任意 $\alpha \in \mathbb{R}$, (lower) level set<br />
$$<br />
S_{\leq \alpha}:= \{x \in \mathbb{R}^n: f(x) \leq \alpha\}<br />
$$ 為 凸集。<br />
===========<br />
<div>
<br /></div>
<b>Proof: </b>若 level set $S_{\leq \alpha}$ 為空集合或者單點集,則陳述自動成立。若不然,取 $x_1,x_2 \in S_{\leq \alpha}$ ,則 $f(x_1) \leq \alpha$ 且 $f(x_2) \leq \alpha$。我們要證明 convex combination of $x_1$ 與 $x_2$ 仍落在 $S_{\leq \alpha}$ 之中,亦即我們要證明 $\lambda x_1 + (1-\lambda)x_2 \in S_{\leq \alpha}$。為此,我們利用 $f$ 的凸性,對任意 $\lambda \in (0,1)$,<br />
\[<br />
f(\lambda x_1 + (1-\lambda) x_2) \leq \lambda f(x_1) + (1-\lambda) f(x_2) \leq \alpha<br />
\]故 $\lambda x_1 + (1-\lambda)x_2 \in S_{\leq \alpha}$,至此得證。$\square$<br />
<br />
<br />
<b>Remark:</b><br />
對於 concave 函數我們仍有類似的結果記錄如下:<br />
<br />
令 $S \subseteq \mathbb{R}^n$ 為凸集,且 $f: S \to \mathbb{R}$ 為 concave 函數,則所有極大點所成的集合 $S^*$ 為 convex set。<br />
<br />
<br />C. H. Hsiehhttp://www.blogger.com/profile/18005098064728038131noreply@blogger.com0tag:blogger.com,1999:blog-3839634717377760340.post-7804967898870480032019-11-09T14:25:00.001-08:002019-11-18T12:21:27.245-08:00[機器學習] 主成分分析 (1)以下我們介紹機器學習/統計學習理論 中把 高維度資料 降維 的一種常用工具,稱作 <b>主成分分析 (Principal Component Analysis)</b>。假設我們有 $n$ 組 $m$ 維度 (去除平均) 資料點集,下圖 顯示 $n=100$ 組 $m=2$ 維 資料點集<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiFYsABxp7rjZICKZsqLNQc7RLjvRWZowck161F70qlmRVdssKzSz09H771Y_Uo11CrEhp14qHCBSJ7DLxlu6F3dnrBNyq2Jald_ZzJunUFiBFrF7J8617wNW4J_vyXIp_q7Nk-VYUAzy74/s1600/PCA_data.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="840" data-original-width="1120" height="300" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiFYsABxp7rjZICKZsqLNQc7RLjvRWZowck161F70qlmRVdssKzSz09H771Y_Uo11CrEhp14qHCBSJ7DLxlu6F3dnrBNyq2Jald_ZzJunUFiBFrF7J8617wNW4J_vyXIp_q7Nk-VYUAzy74/s400/PCA_data.png" width="400" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
注意到上述資料集已經先預先處理使其資料集 中心 在 $(0,0)$。任意(有限維度)資料集皆可預先做此處理將其資料點的平均值 預先 移除。此為主成分分析的首要步驟。<br />
<br />
<br />
<b>主成分分析(Principal Component Analysis):</b><br />
我們的目標為 找到一個向量 ${\bf x} \neq {\bf 0}$ 使得 由此向量所 線性張成(span) 的子空間,記作 $X:=span\{{\bf x}\}$ ,能 最佳適配我們得資料集 (此 subspace $X$ 又稱作 "best line ") 使得\[<br />
\min_{\bf x} \sum_{i=1}^n d_i^2<br />
\]其中 $d_i$ 為第 $i$ 個 資料點 到此 best line (subspace) $X$ 的距離。<br />
<br />
<b>Comments: </b>(1) 此處最佳 "best line" 意指我們要找 ${\bf x}$ 使得 資料點到此 best line 的距離平方最小,此想法可參閱下方示意圖,其中 ${\bf a}_i$ 為代表 第 $i$ 個資料點的向量,$proj_X{\bf a}_i$ 代表 ${\bf a}_i$ 投影到 我們的 subspace $X$ 的投影向量。<br />
<br />
(2) 當然,距離平方最小並不是唯一的選擇,讀者可以考慮使用 $\sum_i |d_i|$ 當作 最佳化的目標函數或者其他種類的目標函數,但為求簡單起見,且符合經典 主成分分析的內容,在此我們僅考慮 距離平方誤差 作為我們的 目標函數。<br />
<br />
(3) 由下圖,讀者不難發現對任意資料向量 ${\bf a}_i$ 而言,此向量 與 subspace $X$ 的 距離平方 $d_i^2$ 可表為<br />
\[<br />
d_i^2 = \| {\bf a}_i - proj_X {\bf a}_i \|_2^2<br />
\]其中 $proj_X {\bf a}_i$ 表示 ${\bf a}_i$ 投影到 subspace $X$ 的向量 。<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgEKjYWdtmAJPxysA_HWZ1WNe8kG4ZASsDeiCu1aV4Mz-M3gdAwiBsxnJAKaZQk9hLvHF1IbHx1toeHCOm9M3F1zDPaAkZydXnrSBKegT233W2EMiMkFUViW0HBmeAKDTn32Nrq-qB1FA5l/s1600/PCA_data.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="840" data-original-width="1120" height="300" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgEKjYWdtmAJPxysA_HWZ1WNe8kG4ZASsDeiCu1aV4Mz-M3gdAwiBsxnJAKaZQk9hLvHF1IbHx1toeHCOm9M3F1zDPaAkZydXnrSBKegT233W2EMiMkFUViW0HBmeAKDTn32Nrq-qB1FA5l/s400/PCA_data.png" width="400" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
<br /></div>
<b>Claim: </b>令資料矩陣<b> </b>\[ A:= \begin{bmatrix} -{\bf a}_1^T- \\ -{\bf a}_2^T- \\ \vdots\\ -{\bf a}_n^T- \end{bmatrix} \in \mathbb{R}^{n \times m} \]則存在 ${\bf x}={\bf v}_1$ 為 1st right-singular vector of $A$ 使得<br />
\[<br />
\min_{{\bf x}} \sum_{i=1}^n d_i^2 = \sigma_2^2+\cdots + \sigma_n^2<br />
\]其中 $\sigma_1$ 為 $A$ 的 1st singular value 。<br />
<br />
<b>Proof: </b>對任意資料向量 ${\bf a}_i \in \mathbb{R}^m$ 而言,${\bf a}_i$ 與 待定向量 ${\bf x} \in X$ 的 距離平方 $d_i^2$ 可表為<br />
\[<br />
\begin{align*}
d_i^2 & = \| {\bf a}_i - proj_{\bf x} {\bf a}_i \|_2^2 \\<br />
&= \bigg\|{\bf a}_i - \frac{ {\bf a}_i^T {\bf x}}{ {\bf x}^T {\bf x} }{\bf x} \bigg\|_2^2\\<br />
& = \bigg\|{\bf a}_i - \frac{ {\bf x}^T {\bf a}_i}{{\bf x}^T {\bf x}}{\bf x} \bigg\|_2^2\\
& = \bigg\|{\bf a}_i - \frac{ {\bf x} ({\bf x}^T {\bf a}_i)}{{\bf x}^T {\bf x} }\bigg\|_2^2\\<br />
& = \bigg\|\bigg( I - \frac{ {\bf x} {\bf x}^T }{{\bf x}^T {\bf x}} \bigg) {\bf a}_i \bigg\|_2^2\\<br />
& = \bigg(\bigg( I - \frac{ {\bf x} {\bf x}^T }{{\bf x}^T {\bf x} } \bigg) {\bf a}_i \bigg)^T \bigg(\bigg( I - \frac{ {\bf x} {\bf x}^T }{{\bf x}^T {\bf x} } \bigg) {\bf a}_i \bigg)\\<br />
& = {\bf a}_i ^T \bigg( I - \frac{ {\bf x} {\bf x}^T }{{\bf x}^T {\bf x}} \bigg)^T \bigg( I - \frac{ {\bf x} {\bf x}^T }{{\bf x}^T {\bf x} } \bigg) {\bf a}_i \\<br />
& = {\bf a}_i ^T \underbrace{\bigg( I - \frac{ {\bf x} {\bf x}^T }{{\bf x}^T {\bf x} } \bigg)^2}_{= I - \frac{ {\bf x} {\bf x}^T }{{\bf x}^T {\bf x}} }{\bf a}_i \\<br />
& = {\bf a}_i ^T \bigg( I - \frac{ {\bf x} {\bf x}^T }{{\bf x}^T {\bf x} } \bigg){\bf a}_i \\<br />
& = {\bf a}_i ^T {\bf a}_i - {\bf a}_i ^T \frac{ {\bf x} {\bf x}^T }{{\bf x}^T {\bf x}}{\bf a}_i \\
\end{align*}<br />
\]注意到
$${\bf a}_i^T{\bf x} {\bf x}^T {\bf a}_i = \underbrace{({\bf a}_i^T{\bf x})}_{\in \mathbb{R}} \underbrace{({\bf x}^T {\bf a}_i)}_{\in \mathbb{R}} ={\bf x}^T ({\bf a}_i {\bf a}_i^T) {\bf x}
$$故
\[
d_i^2 = {\bf a}_i ^T {\bf a}_i - \frac{ {\bf x}^T ( {\bf a}_i {\bf a}_i^T) {\bf x} }{\|{\bf x}\|}<br />
\]
回憶我們的目標是要找到向量 ${\bf x} \neq {\bf 0}$ 使得
\[<br />
\min_{{\bf x}} \sum_{i=1}^n d_i^2<br />
\]上式等價於<br />
\[<br />
\min_{\bf x} \sum_{i=1}^n \bigg( {\bf a}_i ^T {\bf a}_i - \frac{ {\bf x}^T ( {\bf a}_i {\bf a}_i^T) {\bf x} }{{\bf x}^T {\bf x}} \bigg) = n {\bf a}_i ^T {\bf a}_i + \min_{\bf x} \bigg( - \frac{ {\bf x}^T ( \sum_{i=1}^n {\bf a}_i {\bf a}_i^T) {\bf x} }{{\bf x}^T {\bf x}}\bigg)
<br />
\]
注意到第一項與 ${\bf x}$ 無關,利用 $\min_x -f(x)$ 等價為 $\max_x f(x)$ 我們可將上述最佳化問題等價為
\[
\max_{\bf x}\frac{ {\bf x}^T ( \sum_{i=1}^n {\bf a}_i {\bf a}_i^T) {\bf x} }{{\bf x}^T {\bf x}}
\] 由 FACT 1,我們可知<br />
\[
A^T A = \sum_{i=1}^n {\bf a}_i {\bf a}_i^T<br />
\]
故我們最終的最佳化問題為找到向量 ${\bf x}$ 使得<br />
\[<br />
\max_{\bf x} \frac{{\bf x}^T A^T A {\bf x}}{{\bf x}^T {\bf x}} = \max_{\bf x} \frac{\|A {\bf x}\|_2^2}{\|{\bf x}\|_2^2} = \|A\|_2^2 \;\;\;\; (*)<br />
\] 由 下方 FACT 2 可知
\[
\|A \|_2^2 = \sigma_1^2 \] 且 ${\bf x} = {\bf v}_1$, the 1st right-singular vector。此結果非常容易觀察:當 ${\bf x} = {\bf v}_1$ 則 $A{\bf v}_1 = \sigma_1 {\bf u}_1$ 故<br />
\[<br />
\frac{\|A {\bf x}\|_2^2}{\|x\|_2^2} = \frac{\|A {\bf v}_1\|_2^2}{\|{\bf u}_1\|_2^2} = \frac{\sigma_1^2 \|{\bf u}_1\|}{\|{\bf u}_1\|_2^2} = \sigma_1^2<br />
\]故 ${\bf x}={\bf v}_1$ 取到最大值 $\|A \|=\sigma_1^2$,換言之,<br />
\[<br />
\min_{\bf x} \sum_{i=1}^n d_i^2 = (\sigma_1^2+...+\sigma_n^2 )- \sigma_1^2 = \sigma_2^2+\cdots + \sigma_n^2<br />
\] 至此證明完畢。 $\square$<br />
<br />
<br />
<b>Comments</b>:<br />
1. ${\bf v}_1$ 又稱 $A$ 的 第一主成分 (the first principal component of $A$)<br />
<br />
<b>FACT 1: </b>$A:= \begin{bmatrix} -{\bf a}_1^T- \\ -{\bf a}_2^T- \\ \vdots\\ -{\bf a}_n^T- \end{bmatrix} \in \mathbb{R}^{n \times m}$ 則<br />
\[<br />
A^TA = \sum_{i=1}^{n} {\bf a}_i {\bf a}_i^T<br />
\]<br />
<br />
Remark: 上述等式有個非常類似的結果與 矩陣的 trace 有關,我們順道在此紀錄:如果 $A:=\begin{bmatrix}{\bf a}_1 & {\bf a}_2 & \cdots {\bf a}_n \end{bmatrix} \in \mathbb{R}^{m \times n}$ 則<br />
\[<br />
\sum_{i=1}^n {\bf a}_i^T {\bf a}_i = trace(A^TA)<br />
\]<br />
<br />
<b>FACT 2:</b><br />
(a) 任意 $m \times n$ 矩陣 $A$ 的 2-norm $\|A\|_2 = \sigma_1$<br />
(b) 任意 $m \times n$ 矩陣 $A$ 的 Fronbenious norm $\|A\|_F := \sqrt{\sigma_1^2+\sigma_2^2+\cdots + \sigma_n^2}$<br />
<br />C. H. Hsiehhttp://www.blogger.com/profile/18005098064728038131noreply@blogger.com0tag:blogger.com,1999:blog-3839634717377760340.post-52927318384090776932019-11-06T20:56:00.001-08:002019-11-06T21:02:09.292-08:00[線性代數] 一類含有反矩陣的等式<b>Claim:</b><br />
令 $A \in \mathbb{R}^{m \times n}$,且 $\lambda >0$ 則以下等式成立<br />
\[<br />
(A^TA+\lambda I)^{-1}A^T = A^T(AA^T+\lambda I)^{-1}<br />
\]<br />
<br />
<b>Proof: </b>觀察 $A^TAA^T+\lambda A^T$ 可對其從左方或者右方提出 $A^T$,亦即<br />
\[\begin{align*}<br />
A^T(AA^T+\lambda I) = (A^TA+\lambda I)A^T<br />
\end{align*}\]由於 $(AA^T +\lambda I)$ 為可逆,$(AA^T+\lambda I)^{-1}$存在,故對上式兩邊從右方同乘此項可得<br />
\[<br />
A^T = (A^TA+\lambda I)A^T(AA^T+\lambda I)^{-1}<br />
\]又注意到 $(A^TA+\lambda I)$ 為可逆,$(A^TA+\lambda I)^{-1}$存在,對上式從左方同乘此項可得<br />
\[<br />
(A^TA+\lambda I)^{-1}A^T = A^T(AA^T+\lambda I)^{-1}<br />
\]至此證明完畢。$\square$<br />
<br />
<br />
<b>Comments:</b><br />
上述結果多出現於一類稱作 Tikhonov Regularization (或者有拘束的最小二乘方問題)問題之中:亦即令 $A \in \mathbb{R}^{m \times n}$ 且 ${\bf x},{\bf y}\in \mathbb{R}^{n}$,$\lambda >0$考慮<br />
\[<br />
\min_{\bf x}\|A{\bf x} - {\bf y}\|_2^2 + \lambda \|{\bf x}\|_2^2<br />
\]則不難證明上述最佳化問題之解為<br />
\[<br />
{\bf x}= (A^TA+\lambda I)^{-1}A^T {\bf y} = A^T(AA^T+\lambda I)^{-1}{\bf y}<br />
\]上述第二等式成立因為 前述 claim。故我們在實際計算反矩陣時,可以決定到底要用 哪一個 inverse來加速計算速度,比如 $A \in \mathbb{R}^{5000\times 100}$ 那麼 $(A^TA+\lambda I)^{-1}$ 要求對 $100\times 100$ 矩陣做 反矩陣,但是 $(AA^T+\lambda I)^{-1}$ 卻需要對 $5000\times 5000$大小的矩陣來作反矩陣。計算速度上會相差甚遠。<br />
<br />
<br />
<br />
<br />C. H. Hsiehhttp://www.blogger.com/profile/18005098064728038131noreply@blogger.com0tag:blogger.com,1999:blog-3839634717377760340.post-15959594621522118482019-10-07T21:59:00.002-07:002019-10-08T00:05:46.041-07:00[機器學習] 回歸問題應用例:Dow Jones 指數的 回歸模型估計考慮歷史 Dow Jones 指數如下圖所示<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjX3DLJ2JpxyBUawdOgwsIow2B5tnP48gBk6Hhdvi9yg82MMNRzqxsDHAEYE3EvtiguFzXZ6aO16Iyzy39e-7k-cq0QQidRzY_hXxS1B3zVHjja3IOdMku0YFSDJmsKqek4TZFbX6zDHf4B/s1600/DowJones.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" data-original-height="520" data-original-width="705" height="236" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjX3DLJ2JpxyBUawdOgwsIow2B5tnP48gBk6Hhdvi9yg82MMNRzqxsDHAEYE3EvtiguFzXZ6aO16Iyzy39e-7k-cq0QQidRzY_hXxS1B3zVHjja3IOdMku0YFSDJmsKqek4TZFbX6zDHf4B/s320/DowJones.png" width="320" /></a></div>
<br />
令 $v(t)$ 表示 從1795年到 2019年每年的 Dow Jones 指數其中 $t=1,1,\ldots,T$ 且 $t=1$表示 1795年,$t=T$表示至今 (上圖為2019年,但任意年皆可)。由上圖,我們假設 $v_t$ 可由以下 指數函數 近似:亦即 $v: \mathbb{N} \to \mathbb{R}$ 滿足<br />
\[<br />
v(t):= e^{at+b}<br />
\]其中 $t=1,...,T$,$a,b$ 為 待估計參數。我們想問是否能找出 $a,b$ 使得我們可以用此模型來預估未來 Dow Jones 指數的走向:<br />
<br />
上述問題可化簡為回歸問題。首先對 $v_t$ 等式兩邊同取 $\log$,我們可得<br />
\[<br />
\log v(t) = at+b<br />
\]故對任意 $t=1,...,T$我們有<br />
\[<br />
\begin{bmatrix}\log v(1)\\\log v(2)\\ \vdots \\ \log v(T) \end{bmatrix} = \begin{bmatrix}1 & 1 \\ 2 & 1 \\ 3 & 1\\ \vdots & \vdots \\ T & 1 \end{bmatrix} \begin{bmatrix} a\\b\end{bmatrix}<br />
\]<br />
令 ${\bf x}=[a \;\; b]^T$,${\bf b}=\begin{bmatrix}\log v(1) & \log v(2) & \vdots \log v(T) \end{bmatrix}^T$ 且 $$A:=\begin{bmatrix}1 & 1 \\ 2 & 1 \\ 3 & 1\\ \vdots & \vdots \\ T & 1 \end{bmatrix} \in \mathbb{R}^{T \times 2} $$ 則我們得到 $<br />
A{\bf x} = {\bf b}<br />
$ 。由於 $T>>2$,方程 $A{\bf x} = {\bf b}$無解 (參閱 comment 2),但我們可問是否有近似解。為此, 欲求解 ${\bf x}$ 一種常見的手段是採用最小平方法:考慮以下無拘束最小平方最佳化問題<br />
\[<br />
\min_{{\bf x} \in \mathbb{R}^2 }\|A{\bf x} - {\bf b}\|_2^2<br />
\]讀者不難驗證上述問題之解必定滿足以下 normal equation<br />
\[<br />
A^TA{\bf x} = A^T {\bf b}<br />
\]由於 $A$矩陣之 columns 為線性獨立,$A^TA$為 positive definite 其反矩陣存在,故可得解<br />
\begin{align*}<br />
\widehat{{\bf x}}&:=(A^TA)^{-1}A^T{\bf b}<br />
\end{align*}<br />
<br />
<b>Comments:</b><br />
1. 讀者可進一步分析<br />
$$A^TA = \begin{bmatrix}1 & 2& \cdots &T\\ 1 & 1 & \cdots & 1 \end{bmatrix} \begin{bmatrix}1 & 1 \\ 2 & 1 \\ 3 & 1\\ \vdots & \vdots \\ T & 1 \end{bmatrix} = \begin{bmatrix} \sum_{t=1}^T t^2 & \sum_{t=1}^T t \\ \sum_{t=1}^T t & T \end{bmatrix} = \begin{bmatrix} \frac{T(T+1)(2T+1)}{6} & \frac{T(T+1)}{2} \\ \frac{T(T+1)}{2} & T \end{bmatrix}<br />
$$故其反矩陣<br />
\[<br />
(A^TA)^{-1} = \frac{1}{\frac{T^2(T+1)(2T+1)}{6} - \bigg(\frac{T(T+1)}{2} \bigg)^2 } \begin{bmatrix} T & - \frac{T(T+1)}{2} \\ - \frac{T(T+1)}{2} & \frac{T(T+1)(2T+1)}{6} \end{bmatrix}<br />
\]<br />
<br />
<br />
2. 令 $A \in \mathbb{R}^{m\times n}$,${\bf b}\in\mathbb{R}^{m}$,${\bf x} \in \mathbb{R}^n$。考慮 $A{\bf x} = {\bf b}$為一線性系統方程。我們說此系統有解 若且唯若<br />
\[<br />
rank(A) = rank([A|{\bf b}])<br />
\]在上述 Dow Jones 指數的例子中,讀者不難驗證 $rank(A)=2$ 但是 $rank([A|{\bf b}])=3$。故原方程 $A{\bf x} = {\bf b}$無解。<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />
<br />C. H. Hsiehhttp://www.blogger.com/profile/18005098064728038131noreply@blogger.com0tag:blogger.com,1999:blog-3839634717377760340.post-7132298369503663152019-10-04T21:00:00.002-07:002019-10-07T13:19:10.328-07:00[線性代數] 構造 正定矩陣 其元素含有負值的例子首先回憶 <b>正定 (positive definite)</b>矩陣 定義:<br />
<br />
<b>Definition: </b>令 $Q \in \mathbb{R}^{n\times n}$且 $Q^T=Q$。我們說 $Q$ 為 <b>positive definite</b> 若下列條件成立: 對任意 ${\bf x} \in \mathbb{R}^n$ 且 ${\bf x} \neq {\bf 0}$,<br />
$$<br />
{\bf x}^TQ{\bf x}>0<br />
$$<br />
<br />
<br />
我們想問是否有可能構造出一正定矩陣其部分元素取值為負。答案是肯定的。請看以下例子:<br />
<br />
==============<br />
<b>Example: </b><br />
令 $Q = \begin{bmatrix}2 & -1 \\ -1 & 2 \end{bmatrix}$。試証 $Q$ 為 positive definite。<br />
================<br />
<br />
<b>Proof: </b>首先注意到 $Q^T=Q$ 為顯然。故我們僅需証明 對任意 ${\bf x} \neq 0$, ${\bf x}^TQ{\bf x}>0。$為此,取${\bf x}=[x_1\;\;x_2]^T$ 且 $x_1,x_2$不全為零, 觀察<br />
$$<br />
{\bf x}^TQ{\bf x} = [x_1 \;\; x_2] \begin{bmatrix}2 & -1 \\ -1 & 2 \end{bmatrix} \begin{bmatrix}x_1\\x_2 \end{bmatrix} = 2x_1^2+2x_2^2-2x_1x_2$$上述稱為 矩陣二次式(quadratic form)。<br />
<br />
以下我們分幾個情況討論:<br />
<br />
Case 1: 若 $x_2 \neq 0$ 且 $x_1 \neq 0$:<br />
若 $x_1\geq x_2$ ,則 $2x_1^2+2x_2^2-2x_1x_2 \geq 2x_2^2>0$<br />
若 $x_2 \geq x_1$,則 $2x_1^2+2x_2^2-2x_1x_2 \geq 2x_1^2>0$<br />
<br />
Case 2: 若 $x_2 \neq 0$ 且 $x_1 = 0$:則我們有<br />
$$<br />
2x_1^2+2x_2^2-2x_1x_2 = 2x_2^2 > 0<br />
$$<br />
<br />
Case 3: 若 $x_1 \neq 0$ 且 $x_2 = 0$:則我們有<br />
$$<br />
2x_1^2+2x_2^2-2x_1x_2 = 2x_1^2 > 0<br />
$$<br />
綜合以上所述,$Q$ 為 positive definite。至此証明完畢。 $\square$<br />
<br />
<b><br /></b>
<b>Comments:</b><br />
1. 熟習 positive definiteness 性質的讀者可以知道有另一等價定義可以快速檢查 此性質:亦即若對稱矩陣 $Q$ 的 eigenvalue 為正數,則 $Q$ 為 positive definite。上述例子中,$Q$ 的 eigenvalues 不難計算可得 $1,3$ 故滿足此性質,$Q$ 為 positive definite。<br />
<br />
2. 當然,positive definiteness 性質還有諸多其他常用的定義比如 leading principal 或者透過 pivots 在此我們不贅述。C. H. Hsiehhttp://www.blogger.com/profile/18005098064728038131noreply@blogger.com0tag:blogger.com,1999:blog-3839634717377760340.post-54832238874469849932019-06-26T22:25:00.001-07:002019-06-26T22:35:52.185-07:00[三角函數] 一類 離散餘弦取負值的條件<b>Claim 1: </b>令 $\omega \in (0, \pi/2)$,則 存在 正整數 $k $ 使得<br />
\[<br />
\cos(\omega k ) <0<br />
\]==========<br />
<div>
<br /></div>
<br />
<b>Proof: </b>首先回憶 floor 函數:對任意 $x \in \mathbb{R}$, $\lfloor x \rfloor$具備以下性質<br />
\[<br />
x-1 < \lfloor x \rfloor \leq x<br />
\]現在給定 $0 < \omega < \pi/2$,並取<br />
\[<br />
k := 1 + \bigg \lfloor \frac{\pi}{2\omega} \bigg\rfloor<br />
\]則利用前述的 floor 函數性質,我們有<br />
\[<br />
\frac{\pi}{2\omega} < k \leq 1 + \frac{\pi}{2\omega}<br />
\]兩邊同乘 $\omega$ 則<br />
\[<br />
\frac{\pi}{2} < \omega k \leq \omega + \frac{\pi}{2}<br />
\]因為 $\omega \in (0, \pi/2)$,我們可以進一步取上述不等式右方的上界,亦即 $ \omega + \frac{\pi}{2} < \pi$。故<br />
\[<br />
\omega k \in \bigg(\frac{\pi}{2}, \pi \bigg) \subset \bigg( \frac{\pi}{2}, \frac{3\pi}{2}\bigg)<br />
\]注意到對任意 $\theta \in \bigg( \frac{\pi}{2}, \frac{3\pi}{2}\bigg)$, $\cos \theta < 0$ ,故 $\cos(\omega k) < 0$。至此得證。 $\square$<br />
<br />
<br />
<br />
<b>Comment: </b>我們可將 claim 1 結果進一步推廣到包含有相位的情況:<br />
<br />
<br />
<br />
<br />
==========<br />
<b>Claim 2: </b>令 $\omega \in (0, \pi/2)$ 且 $\theta \in (-\pi/2, \pi/2)$,則 存在 整數 $k >2$ 使得<br />
\[<br />
\cos(\omega(k- 1) + \theta) <0<br />
\]==========<br />
<div>
<br /></div>
<br />
<b>Proof: </b>令<br />
\[<br />
k_0 := 1 + \bigg\lfloor \frac{\pi/2 - \varphi}{\omega} \bigg\rfloor<br />
\]則不難驗證 $\omega k_0 + \varphi \in (\pi/2, \pi)$ ,故 $\cos(\omega k_0 + \varphi) <0$。現在若取 $k_1 := k_0 + 1$ 則<br />
\[<br />
\cos(\omega (k_1-1) + \varphi)<0<br />
\]至此得證。 $\square$<br />
<br />
<br />C. H. Hsiehhttp://www.blogger.com/profile/18005098064728038131noreply@blogger.com0tag:blogger.com,1999:blog-3839634717377760340.post-20737824220797065362019-01-04T04:00:00.000-08:002019-01-08T12:44:26.411-08:00[測度論] 關於 Almost Everywhere給定測度空間 $(X,\mathcal{M},\mu)$我們說 <b>某性質 $P$ almost everywhere 成立</b> 意思是 對所有非零測度集合此性質 $P$ 都成立。(換言之,除零測度集之外,此性質 $P$ 都成立。)<br />
<br />
<b>Lemma:</b><br />
假設 $f(x) \geq 0$ 且 $f$ 為 $(\mathcal{M}, \mathcal{B}_{\mathbb{R}})$ 可測。假設 $\int f d\mu = 0$ 則 $f(x) = 0$ almost everywhere (i.e., $\mu\{x: f(x)>0\} = 0$)<br />
<br />
<b>Proof:</b><br />
<b> </b>令 $E:= \{x:f(x)>0\}$,我們要證明<b> </b>$\mu(E) = 0$ 。為此,我們首先證明 $\mu(E_n) = 0$ 其中 $E_n :=\{x: f(x) > 1/n\}$。觀察以下事實 $\cup_n E_n = E$ 且 $E_n \uparrow E$。<br />
<br />
觀察<br />
\[<br />
\mu(E_n) := \int 1_{E_n} \;\;\;\;(*)<br />
\]注意到對任意 $x\in E_n$,我們有 $f(x) > 1/n $,此等同於 $n f(x) > 1$ ,故對任意 $x\in E_n$, $nf(x) 1_{E_n}(x) > 1 \cdot 1_{E_n}(x)$ 。將此用到 $(*)$ 我們得到<br />
\[<br />
\mu(E_n) = \int 1_{E_n} < \int nf(x)1_{E_n} \leq \int nf(x) =n \underbrace{\int f(x) d\mu(x)}_{=0}<br />
\]亦即<br />
\[<br />
\mu(E_n) = 0<br />
\]最後我們檢驗<br />
$$\mu(E) = \mu(\cup_n E_n) = \lim_n \mu(E_n) = 0$$即為所求。$\square$<br />
<br />
<br />
<b>Lemma 2:</b><br />
給定 測度空間 $(X,\mathcal{M}, \mu)$ 且 $\mu$ 為complete measure,若 $f$ 為 $(\mathcal{M},\overline{\mathcal{B}}_{\mathbb{R}})$ measurable 且 $f=g$ almost everywhere 則 $g$ 亦為 $(\mathcal{M},\overline{\mathcal{B}}_{\mathbb{R}})$ measurable。<br />
<br />
<b>Proof:</b><br />
要證明 $g$ 為 $(\mathcal{M},\overline{\mathcal{B}}_{\mathbb{R}})$ measurable,我們令 $I:=[a,\infty] \in \overline{\mathcal{B}}_{\mathbb{R}} $ 且僅需證明<br />
$$<br />
g^{-1}(I) \in \mathcal{M}<br />
$$<br />
為此,我們定義集合<br />
\[<br />
M:=\{x: f(x) \neq g(x)\}<br />
\]且 $M \subset N$ 其中 $N$ 為 null set 滿足 $N \in \mathcal{M}$,亦即 $\mu(N)=0$ (故 $<br />
\mu(M)=0$)。觀察<br />
$$<br />
g^{-1}(I) = \underbrace{(g^{-1}(I) \cap M^c)}_{\in \mathcal{M}} \cup \underbrace{(g^{-1}(I)\cap M)}_{\subset N \in \mathcal{M}} \in \mathcal{M}<br />
$$至此證明完畢。$\square$<br />
<br />
<b>Lemma 3</b><br />
令 $\{f_n\}$ 為在 $(X,\mathcal{M},\mu)$ 上的 measurable 函數數列,若 $\mu$ 為 complete measure,且 $\lim_n f_n(x) = f(x)$ almost everywhere 則 $f$ 為 measurable 。<br />
<br />
<b>Proof:</b><br />
注意到如果 $\lim_n f_n(x) = f(x)$ 逐點收斂,則 $f$ 必然為 measurable (因為 $\lim f_n = \limsup f_n = \liminf_n f_n$ 且 $\limsup f_n$ 與 $\liminf f_n$ 都 measurable)。若 $\lim_n f_n(x) = f(x)$ almost everywhere 令 $N:=\{x: \lim_n f_n(x) \text{ does not exists}\}$ 且 $N \in \mathcal{M}$ 且 $\mu(N)=0$。定義新的函數 $g_n : X \to [-\infty,\infty]$ 滿足<br />
\[ g_n(x):= \begin{cases}<br />
f_n(x) & x \in N^c \\<br />
0 & x \in N<br />
\end{cases}<br />
\]則對任意 $x\in X$,$\lim_n g_n(x)$ 存在,因為<br />
\[ \lim_n g_n(x):= \begin{cases}<br />
f(x) & x \in N^c \\<br />
0 & x \in N<br />
\end{cases} \;\;\;\;(*)<br />
\]將此極限記作 $g(x) := \lim_n g_n(x)$。由於 $N^c,N \in \mathcal{M}$ 故 $g$ 為 mesurable。除此之外,由 $(*)$ 我們得到 $g(x) = f(x)$ almost everywhere。由 Lemma 2 可知 $f$ 為 mesurable。至此證明完畢。 $\square$<br />
<div>
<br /></div>
<br />
<br />
<br />
<br />
<br />
<br />C. H. Hsiehhttp://www.blogger.com/profile/18005098064728038131noreply@blogger.com0tag:blogger.com,1999:blog-3839634717377760340.post-1389597559546280822019-01-04T03:58:00.000-08:002019-01-04T03:58:18.379-08:00[測度論] Almost Uniform Convergence (1) 定義 與 經典例子<b>Definition: </b>令 $f_n, f$ 為 complex-valued measurable 函數,我們說 $f_n \to f$ almost uniformly 若下列條件成立:<br />
對任意 $\varepsilon>0$,存在可測集 $E_\varepsilon$ 滿足 $\mu(E_\varepsilon)<\varepsilon$ 使得<br />
\[<br />
f_n \to f \text{ uniformly on $E_\varepsilon^c$}<br />
\]換言之,$\sup_{x \in X\setminus E_\varepsilon} |f_n(x) - f(x)| < \varepsilon$。<br />
<br />
<b>Example:</b><br />
考慮 測度空間 $([0,1],\mathcal{L},m)$,取 $f_n(x) := x^n$ ,則<br />
1. $f_n \not \to f$ uniformly<br />
2. $f_n \to f$ almost uniformly<br />
<br />
<b>Proof 1.:</b><br />
首先注意到 $$<br />
\lim_n f_n(x) := f(x) = \begin{cases}<br />
0 & x \in [0,1) \\<br />
1 & x = 1<br />
\end{cases}<br />
$$ 觀察 $$<br />
\sup_{x \in [0,1]} |f_n(x) - f(x)| = 1 \not\to 0<br />
$$故 $f_n \not\to f$ uniformly。$\square$<br />
<br />
<b>Proof 2:</b> 令 $\varepsilon \in (0,1)$ 取 $E_\varepsilon :=(1-\varepsilon/2, 1]$ 則 $\mu(E_\varepsilon) = \varepsilon/2 < \varepsilon$ 且對任意 $x \in [0,1] \setminus E_\varepsilon$ 而言,<br />
\begin{align*}<br />
\sup_{x \in [0,1]\setminus E_\varepsilon} |f_n(x) - f(x)| &= \sup_{x \in [0, 1-\varepsilon/2]}|x^n-0|\\<br />
&=(1-\varepsilon/2)^n \to 0 \;\; \text{ as $n \to \infty$}<br />
\end{align*}<br />
至此證明完畢。$\square$C. H. Hsiehhttp://www.blogger.com/profile/18005098064728038131noreply@blogger.com0tag:blogger.com,1999:blog-3839634717377760340.post-58432877855529836252018-12-20T23:25:00.000-08:002019-01-04T03:59:14.234-08:00[測度論] DCT 應用 (2) - Simple Fubini-Tonollei Theorem<b>Theorem:</b><br />
假設 $\{f_n\}\subset L^1$ 使得 $\sum_{n=1}^\infty\int |f_n| <\infty$。則<br />
(a) $\sum_{n=1}^\infty f_n$ almost everywhere 收斂 。<br />
(b) $\int \sum_{n=1}^\infty f_n = \sum_{n=1}^\infty \int f_n$。<br />
<br />
<b>Proof:</b><b>(a) </b>令$\{f_n\}\subset L^1$ 使得 $\sum_{n=1}^\infty\int |f_n| <\infty$,則我們有<br />
\[<br />
\int \sum_{n=1}^\infty |f_n| = \sum_{n=1}^\infty\int |f_n| <\infty<br />
\]故我們知道 $ \sum_{n=1}^\infty |f_n| \in L^1$ 且 $\sum_{n=1}^\infty |f_n|<\infty$ almost everywhere。此表明對 almost every $x$, $\sum_{n=1}^\infty f_n(x) $ (絕對)收斂。令極限<br />
$$
f(x):=\lim_{N\to \infty} \sum_{n=1}^N f_n(x)
$$ 故我們僅需證明此 $f \in L^1$。注意到 對任意 $N$, $\lim_N \sum_{n=1}^N f_n \leq \lim_N \sum_{n=1}^\infty |f_n|$ a.e. 故 $f \leq \lim_N \sum_{n=1}^N |f_n|$ a.e. 由於 $\lim_N \sum_{n=1}^N |f_n| \in L^1$ 故 $f \in L^1$。<br />
<br />
<b>Proof (b)</b><br />
要證明 $\int \sum_{n=1}^\infty f_n = \sum_{n=1}^\infty \int f_n$。首先觀察<br />
\[<br />
\int \sum_{n=1}^N f_n = \sum_{n=1}^N \int f_n \;\;\;\; (*)<br />
\]由於 $\sum_{n=1}^N f_n \leq \sum_{n=1}^\infty |f_n| \in L^1$ 且 $\sum_{n=1}^N f_n \to f$ a.e. in $L^1$ ,由 Dominated Convergence Theorem 我們有\[<br />
\lim_{N\to \infty} \int \sum_{n=1}^N f_n = \int \lim_{N\to \infty}\sum_{n=1}^N f_n = \int \sum_{n=1}^\infty f_n\;\;\;\; (**)<br />
\]故對 $(*)$兩邊同取極限並利用上述結果 $(**)$ 可得<br />
\[<br />
\int \sum_{n=1}^\infty f_n = \sum_{n=1}^\infty \int f_n<br />
\]至此證明完畢。$\square$<br />
<br />
<br />
<br />
<br />C. H. Hsiehhttp://www.blogger.com/profile/18005098064728038131noreply@blogger.com0tag:blogger.com,1999:blog-3839634717377760340.post-86718570726753324852018-12-11T03:58:00.000-08:002019-01-04T03:58:50.969-08:00[測度論] indicator function 為可測函數的充分必要條件令 $(X,\mathcal{M})$ 與 $(\mathbb{R},\mathcal{L})$ 為可測空間。<br />
<br />
<b>Fact: </b>令 $1_E: (X,\mathcal{M}) \to (\mathbb{R},\mathcal{L})$ 滿足<br />
\[ 1_E(x):=\begin{cases}<br />
1 & x \in E\\<br />
0 & x \notin E<br />
\end{cases}<br />
\]則 $1_E$ 為可測函數 若且唯若 $E \in \mathcal{M}$。<br />
<div>
<br /></div>
<div>
<b>Proof:</b></div>
$(\Leftarrow)$ 假設 $E \in \mathcal{M}$。我們要證明 $1_E$ 為可測函數。為此,令 $I:=(-\infty, \alpha]$ 為任意區間,我們僅需證明 $1_E^{-1}(I) \in \mathcal{M}$。若 $\alpha \leq 0$,則<br />
$$<br />
1_E^{-1}(I) =\{x:1_E(x) < \alpha\}=\varnothing \in \mathcal{M}<br />
$$ 若 $\alpha >1$ 則<br />
$$<br />
1_E^{-1}(I) =\{x:1_E(x)<\alpha\}=X \in \mathcal{M}<br />
$$最後,若 $0<\alpha \leq 1$ 則<br />
$$<br />
1_E^{-1}(I) =\{x:1_E(x)<\alpha\}=E^c<br />
$$ 由於 $E\in \mathcal{M}$ 且 $\mathcal{M}$ 為 $\sigma$-algebra,故 $E^c \in \mathcal{M}$。至此我們得證 $1_E$ 為可測函數。<br />
<br />
$(\Rightarrow)$ 假設 $1_E$ 為可測函數,我們要證明 $E \in \mathcal{M}$。由於 $1_E$ 為可測函數,對任意區間 $I=(-\infty,\alpha]$ 而言,$1_E^{-1}(I) \in \mathcal{M}$。故取 $\alpha =1/2$ 我們有<br />
$$<br />
1_E^{-1}(I):=\{x:\chi_E(x)<1/2\} = E^c \in \mathcal{M}<br />
$$由於 $\cal M $為 $\sigma$-algebra,故 $E\in \mathcal{M}$。$\square$C. H. Hsiehhttp://www.blogger.com/profile/18005098064728038131noreply@blogger.com0tag:blogger.com,1999:blog-3839634717377760340.post-54620006729872519312018-11-14T09:37:00.000-08:002019-01-04T03:59:38.469-08:00[測度論] 有限測度空間中,$f_n\to f$ a.e. $\Rightarrow f_n \to f$ in measure考慮測度空間 $(X,\mathcal{M},\mu)$<br />
<b>Theorem: </b>令 $\mu(X) <\infty$ 且 $f_n \to f$ a.e. 則 $f_n \to f$ in measure。<br />
<b>Proof:</b><br />
不失一般性的情況下,假設 $f_n \to f$ everywhere。令 $\alpha > 0$ 我們要證明<br />
\[<br />
\lim_{n}\mu(x: |f_n(x) - f(x)| \geq \alpha ) = 0<br />
\]因為 $f_n \to f$ everywhere (i.e., $f_n \to f$ pointwise) 由極限定義,我們知道給定任意 $\varepsilon >0$ 存在 $N:=N(x)>0$ 使得當 $n\geq N$,<br />
\[<br />
|f_n(x) - f(x)| \leq \varepsilon<br />
\]這表明<br />
\[<br />
x \in \bigcup_N \bigcap_{n \geq N(x)} \{|f_n(x) - f(x)|\leq \varepsilon\}<br />
\]且<br />
\[<br />
X:= \bigcup_N \bigcap_{n \geq N(x)} \{|f_n(x) - f(x)|\leq \varepsilon\}<br />
\]故<br />
\[<br />
X^c = \emptyset = \bigcap_N \bigcup_{n\geq N(x)} \{|f_n(x) - f(x)|> \varepsilon\}<br />
\]令 $E_N:= \bigcup_{n\geq N(x)} \{|f_n(x) - f(x)|> \varepsilon\} $ 且注意到 $E_N$ 對 $N$ 遞減,且 $\mu(X) <\infty$ 由 測度的 下連續性,我們有<br />
\[<br />
\underbrace{\mu(\cap_N E_N)}_{=\mu(\emptyset)=0} = \lim_N \mu(E_N)<br />
\]故我們得到<br />
\[<br />
\mu(E_N) = \mu(\bigcup_{n \geq N(x)} \{|f_n(x) - f(x)|> \varepsilon\}) \to \mu(\emptyset) = 0<br />
\]將其換成較小的集合上述結果仍然成立,亦即<br />
\[<br />
\mu( \{|f_n(x) - f(x)|> \varepsilon\}) \to 0<br />
\]此表明 $f_n \to f$ in meausre。至此證明完畢。C. H. Hsiehhttp://www.blogger.com/profile/18005098064728038131noreply@blogger.com0tag:blogger.com,1999:blog-3839634717377760340.post-15527347761314250452018-10-12T08:38:00.000-07:002019-10-08T13:25:41.095-07:00[線性代數] 若 $A$ 有線性獨立的 columns 則 $A^TA$ 為 symmetric 且 positive definite<b>Definitions:</b><br />
1. 我們說一個矩陣 $A$ 為 symmetric 若 $A^T=A$<br />
2. 我們說一個矩陣 $A \in \mathbb{R}^{n \times n}$ 為 正定 (positive definite) 若 對任意 ${\bf x} \in \mathbb{R}^n, \; {\bf x} \neq 0$ 而言,<br />
\[<br />
{\bf x}^T A {\bf x} >0<br />
\]<br />
<b>Comments:</b><br />
上述positive definite 建構的 ${\bf x}^T A {\bf x} $ 稱作 矩陣的二次式。<br />
判斷矩陣正定的方式有許多,上述只是其中一種,另外還有許多等價定義。下列敘述等價<br />
1. 矩陣 $A$ 為 positive definite<br />
2. 對任意 ${\bf x} \in \mathbb{R}^n, \; {\bf x} \neq 0$ 而言,${\bf x}^T A {\bf x} >0$<br />
3. 矩陣 $A$ 有 正的 特徵值(eigenvalues)<br />
4. 矩陣 $A$ 有 正的 leading principal minors<br />
5. 矩陣 $A$ 有 正 的 pivots<br />
<div>
<br />
<br />
<br /></div>
接著我們給出當 $A$ 非方陣的時候,如何找出其對應的 正定矩陣。<br />
<br />
<br />
<br />
==========<br />
<b>Theorem:</b><br />
$A \in \mathbb{R}^{m\times n}$ 有線性獨立的 columns 則 $A^TA$ 為 symmetric 且 positive definite<br />
==========<br />
<b>Proof:</b><br />
首先證明 $A^TA$ 為 symmetric。觀察 $(A^TA)^T = A^TA$故得證。<br />
<br />
接著證明 $A^TA$ 為 positive definite。令 ${\bf x} \in \mathbb{R}^n, \; {\bf x} \neq 0$ ,觀察<br />
\[<br />
x^TA^TAx = (Ax)^T(Ax) = \|Ax\|^2<br />
\]我們要證明 $\|Ax\|^2>0$,利用反證法:假設若不然,亦即 $\|Ax\|^2 =0$ ,由於因為 $A$ 有線性獨立(linear independent)的 column,記作 ${\bf a}_1,{\bf a}_2,...,{\bf a}_n$ 故由線性獨立的定義,<br />
\[<br />
A{\bf x} = x_1 {\bf a}_1 + x_2 {\bf a}_2 + \cdots x_n {\bf a}_n = {\bf 0}<br />
\]若且唯若 $x_1= x_2 = ... x_n = 0$ 此與原本假設 ${\bf x} \neq 0$ 矛盾,故 $\|Ax\|^2>0$。$\square$<br />
<br />
<br />
<b>Theorem 2:</b><br />
任意 positive definite matrix 為 invertible<br />
<br />
<b>Proof:</b> 令 $A$ 為 positive definite matrix。利用反證法,假設<b> </b>$A$ 的反矩陣不存在,此表示存在 ${\bf x} \neq {\bf 0}$ 使得 $A{\bf x} = {\bf 0}$。現在觀察<br />
\[<br />
{\bf x}^T A{\bf x} = \underbrace{{\bf x}^T {\bf 0}}_{={\bf 0}} \;\;\;\;\;(**)<br />
\]但是由於 $A$為 positive definite,我們知道對任意非零向量 ${\bf x}$,${\bf x}^TA{\bf x} > 0$此與 式 $(**)$ 矛盾。故 $A$ 反矩陣存在,換言之$A$ 為 invertible。$\square$<br />
<br />
<br />
<br />
<b>Theorem 3:</b><br />
若 $A^TA$ 為 invertible,則 $A$ 具有 線性獨立 columns。<br />
<b><br /></b>
<b>Proof:</b><br />
令 $A:=[{\bf a}_1 \;\; \cdots \;\; {\bf a}_n]$ 其中 ${\bf a}_i$ 為 $A$ 的 columns。我們要證明<br />
$$<br />
\sum_{i=1}^n x_i {\bf a}_i ={\bf 0} \Rightarrow x_i = 0,\;\; \forall i<br />
$$ 注意到對任意 $x_i$,$\sum_{i=1}^n x_i {\bf a}_i ={\bf 0}$ 表示<br />
\[<br />
A{\bf x} = {\bf 0}<br />
\]其中 ${\bf x}:=[x_1\;\;x_2\;\;\cdots x_n]^T$。故<br />
\[<br />
A^T A{\bf x} = A^T {\bf 0} = {\bf 0}<br />
\]由於 $A^TA$ 為 invertible,故 ${\bf x}={\bf 0}$,亦即 $x_i = 0, \;\; \forall i$ 。至此證明完畢。$\square$<br />
<br />
<br />
<br />
<b>Comments:</b><br />
相關文章參閱:<a href="https://ch-hsieh.blogspot.com/2010/01/blog-post.html" target="_blank">[線性系統] 矩陣的二次式 與 正定矩陣</a><br />
<br />
<br />C. H. Hsiehhttp://www.blogger.com/profile/18005098064728038131noreply@blogger.com0tag:blogger.com,1999:blog-3839634717377760340.post-37243468790425172612018-09-08T08:12:00.004-07:002018-09-08T08:30:32.128-07:00[泛函分析] 幾何平均與算術平均不等式的一類推廣回憶中學時期學過的 幾何平均與算術平均關係:令 $a,b \in \mathbb{R}$則 幾何平均 有 算術平均作為上界<br />
\[<br />
\sqrt{ab} \leq \frac{a+b}{2}<br />
\]現在我們將上述結果做一類推廣<br />
<br />
<b>Claim: </b>令 $\theta \in (0,1)$ 且 $a, b \geq 0$則<br />
\[<br />
a^{1-\theta}b^{\theta} \leq (1-\theta)a + \theta b<br />
\]<br />
在給出證明之前我們先做出一些說明<br />
<br />
<b>Remarks:</b><br />
1. 上述 claim 不等式左方:$a^{1-\theta}b^{\theta}$ 一般稱作廣義幾何平均 (Generalized Geometric Mean)。<br />
2. 上述 claim 不等式右方:$(1-\theta)a + \theta b$ 有些學者將其稱作廣義算術平均 (Generalized Arthmic Mean)。但若有涉獵凸分析或者凸最優問題的讀者大概不難看出 此式具備 convex combinaiton 的形式。事實上此不等式在 與凸分析中的 log-convexity 有相關,讀者可自行查閱相關文獻。<br />
3. 上述 Claim 一般又稱作 Auxiliary Holder inequality.<br />
<br />
以下我們給出 Claim 的證明。<br />
<br />
<b>Proof of the Claim: </b>首先做以下觀察:若 $a,b = 0$ 或任一為 $0$ 則不等式自動成立。故在不失一般性的情況下 我們設 $a \geq b >0$ 並且注意到 $a^{1-\theta} = a a^{-\theta}$ 故我們可改寫要證明的不等式如下<br />
\begin{align*}<br />
\left(\frac{b}{a}\right)^\theta \leq (1-\theta) + \theta \frac{b}{a}<br />
\end{align*}<br />
令 $x:=b/a$ 則 $x \in (0,1)$ 且我們僅需證明<br />
\[<br />
x^\theta \leq (1-\theta) +\theta x<br />
\]令 $g(x):= 1-\theta +\theta x - x^\theta $,注意到 $g(1) = 0$ 且 $g(0) = 1-\theta>0$<br />
\[<br />
g'(x) = \theta -\theta x^{\theta-1} < \theta -\theta = 0<br />
\]亦即 $g'(x) <0$ 表示 $g$ 為在 $x \in (0,1)$ 處為遞減函數。故由 $g$ 的連續性,對 $x \in [0,1]$ 我們有<br />
\[<br />
g(x) \geq 0<br />
\]此等價為<br />
\[<br />
1-\theta +\theta x - x^\theta \geq 0<br />
\]同理<br />
\[<br />
x^\theta \leq (1-\theta) +\theta x<br />
\]上述即為我們待證的不等式,至此證明完畢。$\square$C. H. Hsiehhttp://www.blogger.com/profile/18005098064728038131noreply@blogger.com0tag:blogger.com,1999:blog-3839634717377760340.post-24590349788851964722018-07-11T20:21:00.000-07:002018-10-11T20:22:13.180-07:00[測度論] Dominated Convergence Theorem<b>Theorem: Dominated Convergence Theorem DCT (real-valued functions)</b><br />
令 sequence $\{f_n\} \subset L^1$ 滿足<br />
(a) $f_n \to f$ almost everywhere<br />
(b) 存在非負函數 $g \in L^1$ 使得 $|f_n| \leq g$ almost everywhere for all $n$<br />
則\[<br />
f \in L^1<br />
\]且<br />
\[<br />
\lim_n \int f_n =\int f<br />
\]<br />
<b>Proof: </b> 先證 $f \in L^1$:<b>由於 </b>$f_n \to f$ almost everywhere 且 $f_n \in L^1$,可知 $f $ measurable (see Proposition 2.11/2.12 )。由於 $|f_n| \leq g$ almost everywhere 故 $|f| \leq g$ almost everywhere,故 $f \in L^1$。<br />
<br />
接著我們證 $\lim_n \int f_n =\int f$:注意到 $|f_n| \leq g$ almost everywhere,故我們有<br />
\[<br />
-g \leq f_n \leq g \text{ almost everywhere}<br />
\]換言之,我們有<br />
\[<br />
f_n + g \geq 0\text{ almost everywhere}<br />
\]與<br />
\[<br />
g-f_n \geq 0 \text{almost everywhere}<br />
\]也就是說 $\{f_n + g\}, \{g-f_n\} \in L^+$。由 Fatou Lemma 我們有<br />
\[<br />
\begin{gathered}<br />
\int {\mathop {\lim \inf }\limits_n } ({f_n} + g) \leqslant \lim \inf \int {({f_n} + g)} ; \hfill \\<br />
\int {\mathop {\lim \inf }\limits_n } (g - {f_n}) \leqslant \lim \inf \int {(g - {f_n})} \hfill \\<br />
\end{gathered} \;\;\; (*)<br />
\]注意到上述積分不等式左方,積分項有以下結果 (利用 limsup or liminf 的性質),我們有 $\mathop {\lim \inf }\limits_n \left( {{f_n} + g} \right) = g + \mathop {\lim \inf }\limits_n {f_n}$ 以及 $$\mathop {\lim \inf }\limits_n \left( {g - {f_n}} \right) = g + \mathop {\lim \inf }\limits_n \left( { - {f_n}} \right) = g - \mathop {\lim \sup }\limits_n {f_n}<br />
$$同理,對於積分不等式右方,我們有<br />
\[\lim \inf \int {({f_n} + g)} = \lim \inf \left( {\int {{f_n} + \int g } } \right) = \lim \inf \int {{f_n} + \int g } \]與<br />
\[\lim \inf \int {(g - {f_n}) = \int {g + \lim \inf \left( { - \int {{f_n}} } \right)} = \int {g - \lim \sup \int {{f_n}} } } \]<br />
將此結果帶入 $(*)$ 我們有<br />
\begin{align*}<br />
&\left\{ \begin{gathered}<br />
\int {\mathop {\lim \inf }\limits_n } ({f_n} + g) \leqslant \lim \inf \int {({f_n} + g)} ; \hfill \\<br />
\int {\mathop {\lim \inf }\limits_n } (g - {f_n}) \leqslant \lim \inf \int {(g - {f_n})} \hfill \\<br />
\end{gathered} \right. \hfill \\<br />
&\Rightarrow \left\{ \begin{gathered}<br />
\int g + \int {\mathop {\lim \inf }\limits_n } {f_n} \leqslant \lim \inf \int {{f_n} + \int g } ; \hfill \\<br />
\int g - \int {\mathop {\lim \sup }\limits_n {f_n}} \leqslant \int {g - \lim \sup \int {{f_n}} } \hfill \\<br />
\end{gathered} \right. \hfill \\<br />
&\Rightarrow \left\{ \begin{gathered}<br />
\int {\mathop {\lim \inf }\limits_n } {f_n} \leqslant \lim \inf \int {{f_n}} ; \hfill \\<br />
- \int {\mathop {\lim \sup }\limits_n {f_n}} \leqslant - \lim \sup \int {{f_n}} \hfill \\<br />
\end{gathered} \right. \hfill \\<br />
\end{align*} 注意到 $f = \lim_n f_n = \liminf_n f_n = \limsup_n f_n$ ,而且 $\{x: \lim_n f_n \neq f(x)\}$ 的測度為 $0$,故 $\int f = \int \liminf f_n = \int \limsup f_n$。 現在我們進一步改寫上式<br />
\[\begin{gathered}<br />
\left\{ \begin{gathered}<br />
\int f \leqslant \lim \inf \int {{f_n}} ; \hfill \\<br />
\int f \geqslant \lim \sup \int {{f_n}} \hfill \\<br />
\end{gathered} \right. \hfill \\<br />
\Rightarrow \lim \sup \int {{f_n} \leqslant \int {f \leqslant \lim \inf \int {{f_n}} } } \hfill \\<br />
\end{gathered} \]亦即 $\int f_n \to \int f$。至此得證。$\square$<br />
<br />
<br />
<br />
<b>Remarks:</b><br />
$\liminf (a_k + b+k) = \liminf a_k + \liminf b_k$ 不全為然。Counter example?<br />
<br />
上述等式成立僅僅 $\lim a_k = a$ 則 $\liminf_k (a_k + b_k) = a+\liminf b_k$。<br />
<br />
<br />
<br />C. H. Hsiehhttp://www.blogger.com/profile/18005098064728038131noreply@blogger.com0tag:blogger.com,1999:blog-3839634717377760340.post-32172806818468564202018-06-27T12:30:00.001-07:002018-07-24T10:04:17.740-07:00[最佳化] 對原最佳化問題的解是否能"回收"使用到新最佳化問題令 $J: \mathbb{R}^n \to \mathbb{R}$ ,考慮以下最佳化問題<br />
\[<br />
\min_{x_1,x_2,...x_n} J(x_1,x_2,...x_n) := J(x_1^*,x_2^*,...,x_n^*)<br />
\]上述 $x_i^*$ 表示最佳解。現在考慮新的目標函數 $G: \mathbb{R}^n \to \mathbb{R}$ 為 上述的 $J:\mathbb{R}^n \to \mathbb{R}$ 額外加上新的函數 $F: \mathbb{R}^n \to \mathbb{R}$,亦即<br />
\[<br />
G(x_1,x_2,...,x_n) :=J(x_1,x_2,...,x_n) + F(x_1,x_2,...,x_n)<br />
\]我們想問前述獲得的最佳解 $x_1^*,x_2^*,.., x_n^*$ 是否仍然對新的目標函數成立?換句話說,是否能夠 "回收" 之前已經算好的最佳解 $ x_i^*$ 用在新的目標函數 $G$ 上呢。答案是否定的。考慮以下一個簡單的反例<br />
<br />
<b>Example:</b><br />
對 $i=1,2,$,令 $x_i \in [-1,1]$並且將所有符合此條件的 $x_i$ 所成之集合記作 $\mathcal{X}$。現在考慮目標函數 $J(x_1,x_2) := x_1^2+x_2^2$ 並且 我們要求<br />
$$<br />
\min_{x_1,x_2 \in \mathcal{X}} J(x_1,x_2) = \min_{x_1,x_2 \in \mathcal{X}}x_1^2+x_2^2<br />
$$則最佳解不難發現為 $x_1^*=x_2^*=0$。現在我們考慮新的目標函數,將其記作<br />
$$<br />
G(x_1,x_2) :=J(x_1,x_2) + x_2<br />
$$亦即 $G$ 為舊的目標函數 $J$ 額外加上 線性函數 $x_2 $。我們要求<br />
$$<br />
\min_{x_1,x_2 \in \mathcal{X}} G(x_1,x_2) = \min_{x_1,x_2 \in \mathcal{X}} x_1^2+x_2^2 + x_2<br />
$$其最佳解變成 $x_1^* = 0$ 但 $x_2^* = -1/2 \;\;\; ( \neq 0)$。亦即舊的最佳解不能被"回收"使用。<br />
<br />
<b>Comments:</b><br />
1. 上述謬誤偶爾能在文獻中發現。讀者應小心並盡量避免犯此錯誤。<br />
2. 上述例子中若要使原最佳解可以被回收使用到新最佳解有很多方法,比如限制 可行集 $\mathcal{X}$ 將其改為 $0 \leq x_i \leq 1$ 便是一種。但是否符合需求又是另外一層考量。<br />
3. 上述例子中若把 $\mathcal{X} := \mathbb{R}^2$,則有拘束最佳化問題變成無拘束最佳化問題,但反例仍然成立。<br />
<br />
<br />C. H. Hsiehhttp://www.blogger.com/profile/18005098064728038131noreply@blogger.com0tag:blogger.com,1999:blog-3839634717377760340.post-75493437826674440882018-05-09T10:55:00.000-07:002018-05-09T10:55:00.110-07:00[測度論] 何時 兩可測函數相乘之積分 會與 個別先做積分後再相乘 相等? <b>Theorem: </b><br />
令 $(X,\mathcal{M,\mu})$ 與 $(Y, \mathcal{N},\nu)$ 為任意測度空間。<br />
(a) 若 $f: X \to \mathbb{R}$ 為 $\mathcal{M}$-measurable 且 $g: Y \to \mathbb{R}$ 為 $\mathcal{N}$-measurable 且我們定喔 $h(x,y):=f(x)g(y)$ 則 $h$ 為 $\mathcal{M} \otimes \mathcal{N}$-measurable。<br />
(b) 若 $f \in L^1(\mu)$ 且 $g \in L^1(\nu)$,則 $h \in L^1(\mu \times \nu)$ 且<br />
\[<br />
\int h \; d(\mu \times \nu) = \left( \int f d\mu \right) \left( \int g d \nu \right)<br />
\]<br />
<br />
<b>Proof (a):</b><br />
令 $a \in \mathbb{R}$,考慮 $A:=[a,\infty) \in \mathcal{B}_{\mathbb{R}}$我們要證明<br />
\[<br />
h^{-1}(A) \in \mathcal{M} \otimes \mathcal{N}<br />
\]注意到因為 $f: X \to \mathbb{R}$ 為 $\mathcal{M}$-measurable 且 $g: Y \to \mathbb{R}$ 為 $\mathcal{N}$-measurable ,我們有 $f^{-1}([a,\infty)) \in \mathcal{M}$ 與 $g^{-1}([a,\infty)) \in \mathcal{N}$ 。<br />
<br />
現在定義兩個新函數 $F,G: X\times Y \to \mathbb{R}$ 分別滿足 $F(x,y) := f(x), \forall y \in Y$ ,$G(x,y):=g(y), \forall x \in X$,則我們可知 $h $ 為 $F$ 與 $G$ 相乘,亦即 $h=FG$。現在觀察<br />
\begin{align*}<br />
{F^{ - 1}}(A) &= \left\{ {(x,y) \in X \times Y:F(x,y) \in [a,\infty )} \right\} \\<br />
& = \left\{ {(x,y) \in X \times Y:f\left( x \right) \in [a,\infty ),\forall y \in Y} \right\} \\<br />
& = \left\{ {x \in X:f\left( x \right) \in [a,\infty )} \right\} \times Y \\<br />
& = \underbrace {{f^{ - 1}}\left( {[a,\infty )} \right)}_{\in \mathcal M} \times \underbrace Y_{ \in {\mathcal N}} \in {\mathcal M} \otimes {\mathcal N}<br />
\end{align*}<br />
同理<br />
\begin{align*}<br />
{G^{ - 1}}(A) &= \left\{ {(x,y) \in X \times Y: G(x,y) \in [a,\infty )} \right\} \\<br />
& = \left\{ {(x,y) \in X \times Y:g\left( x \right) \in [a,\infty ),\forall x \in X} \right\} \\<br />
& = X \times \left\{ {y \in Y : g\left( x \right) \in [a,\infty )} \right\} \\<br />
& = \underbrace X_{ \in {\mathcal M}} \times \underbrace {{g^{ - 1}}\left( {[a,\infty )} \right)}_{ \in {\mathcal N}} \in {\mathcal M} \otimes {\mathcal N}<br />
\end{align*}亦即,$F,G \in \mathcal{M} \otimes \mathcal{N}$,故由 相乘保證 measurability 性質可知 $FG \in \mathcal{M} \otimes \mathcal{N}$,亦即 $h \in \mathcal{M} \otimes \mathcal{N}$。<br />
<br />
<b>Proof (b): </b>首先證明 $h \in L^1(\mu \times \nu)$,亦即要證<br />
\[<br />
\int |h| d(\mu \times \nu) < \infty<br />
\]由於 $|h| \in L^+(X \times Y)$,故由 Tonelli Theorem 可知<br />
\[<br />
\int |h| d(\mu \times \nu) = \int \int |f(x)| |g(y)| d \mu(x) d\nu(y) <\infty<br />
\]上述不等式成立因為 $f \in L^1(\mu)$ 與 $g \in L^1(\nu)$。故 $h \in L^1(\mu \times \nu)$。<br />
<br />
接著由於 $h \in L^1$ ,利用 Fubini theorem 我們可寫<br />
\[<br />
\int h d(\mu \times \nu) = \int \int FG d\mu d\nu = \int f(x) d\mu(x) \int g(x) d\nu(y)<br />
\]即為所求。$\square$C. H. Hsiehhttp://www.blogger.com/profile/18005098064728038131noreply@blogger.com0