[線代] Sparse近似最佳化問題

看板Math作者znmkhxrw (QQ)時間8年前 (2016/06/17 00:26)推噓2(2推 0噓 21→)

留言23則, 2人參與討論串1/2 (看更多)

請問下面(a),(b)兩個最佳化問題的等價性關係為何?? (在某篇paper看到有關overcomplete representation，不過不是數學文章，所以很多式子跟定義我查很久，也有關Ax=b的解的機率分布，之後找了reference與sparse等等會有這問題僅是源自一個最佳化他簡單一句話就說等價於下一個最佳化...好不顯然QQ 找資料跟自己證就越來越多東西，條件也不太夠之類的) Notation：║x║= euclidean norm , x€R^n A^t = transpose of A A^+ = pseudo inverse of A (Moore-Penrose inverse) --------------------------------------------------------------- (a) Let A€M_mxn(R), b€R^m, λ>0. We consider inf {║Ax-b║^2 + λ║x║^2：x€R^n } Q1：是否存在x€R^n 剛好等於inf Q2：如果存在，是否唯一 Ans：(自己證的，應該沒錯XD) Yes, this x = (A^tA + λI)^(-1) A^t b (b) Let A€M_mxn(R), b€R^m. Assume system Ax = b is consistent. We consider (有解) inf {║x║^2：Ax = b, x€R^n } Q1：是否存在x€R^n 剛好等於inf Q2：如果存在，是否唯一 Ans：(即線代關於最小範數解的內容) Yes, this x = A^+ b ------------------------------------------------------ 問題來了，因為原始paper與後來找的reference都大同小異，有重疊也有不同的地方甚至最佳化的內容也不太一樣，有些是1 norm，有些是p norm 然後沒有證明就說他們等價，所以才想證證看以上面說的(a),(b)為例，所謂的等價，是否是：如果Ax=b有解，存在唯一一個正數λ，使得(a),(b)找到的x是一樣的 ( <Note> 在(a)中Ax=b不一定有解，只是有解時才有機會跟(b)等價 ) 如果是如此的話，有幾個問題： 1.怎麼證存在唯一一個正數λ 2.(a),(b)就算得出共同的x，其值會一樣嗎？還是不重要？ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.231.124.20 ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1466094362.A.6F1.html

推