2.2 \u4e8c\u9636\u5dee\u5206\u77e9\u9635<\/h3>\n
\u5bf9\u4e8e\u957f\u5ea6\u4e3a n \u7684\u4fe1\u53f7\uff0c\u4e8c\u9636\u5dee\u5206\u77e9\u9635 D \u7684\u5f62\u5f0f\u4e3a\uff1a<\/p>\n
$$D = \\begin{bmatrix}
\n1 & -2 & 1 & 0 & \\cdots & 0 \\\\
\n0 & 1 & -2 & 1 & \\cdots & 0 \\\\
\n\\vdots & \\ddots & \\ddots & \\ddots & \\ddots & \\vdots \\\\
\n0 & \\cdots & 0 & 1 & -2 & 1
\n\\end{bmatrix} \\in \\mathbb{R}^{(n-2)\\times n}$$<\/p>\n
3. \u95ee\u9898\u8f6c\u5316\u4e0e\u6c42\u89e3<\/h2>\n3.1 \u5f15\u5165\u8f85\u52a9\u53d8\u91cf<\/h3>\n
\u7531\u4e8e L1 \u8303\u6570\u4e0d\u6613\u76f4\u63a5\u4f18\u5316\uff0c\u5f15\u5165\u8f85\u52a9\u53d8\u91cf v\uff0c\u5c06\u95ee\u9898\u8f6c\u5316\u4e3a\uff1a<\/p>\n
\uff08\u5176\u4e2d\u8f85\u52a9\u53d8\u91cf\u7528\u4e8e\u8868\u8fbe\u5dee\u5206\u7684\u4e0a\u754c\uff0c\u9650\u5236\u53d8\u5316\u5e45\u5ea6\uff0c\u7528\u4e8e\u5c06\u5b9e\u9645\u95ee\u9898\u8f6c\u5316\u4e3a\u6700\u4f18\u5316\u8303\u56f4\u5185\u7684\u95ee\u9898\uff09<\/p>\n
$$\\begin{aligned}
\n\\min_{x,v} & \\quad \\frac{1}{2}||x - y||_2^2 + \\lambda\\sum_i v_i \\\\
\ns.t. & \\quad -v \\leq Dx \\leq v
\n\\end{aligned}$$<\/p>\n
3.2 \u62c9\u683c\u6717\u65e5\u5bf9\u5076\u95ee\u9898<\/h3>\n
\u6784\u5efa\u62c9\u683c\u6717\u65e5\u51fd\u6570\uff08\u5c06\u7ea6\u675f\u8f6c\u5316\u81f3\u6c42\u89e3\u65b9\u7a0b\u5185\uff09\uff1a<\/p>\n
$$L(x,v,\\mu_1,\\mu_2) = \\frac{1}{2}||x - y||_2^2 + \\lambda\\sum_i v_i + \\mu_1^T(Dx - v) + \\mu_2^T(-Dx - v)$$<\/p>\n
3.3 \u6807\u51c6\u4e8c\u6b21\u89c4\u5212\u5f62\u5f0f<\/h3>\n
\u5c06\u62c9\u683c\u6717\u65e5\u51fd\u6570\u8f6c\u5316\u4e3a\u6807\u51c6\u4e8c\u6b21\u89c4\u5212\u95ee\u9898\uff1a<\/p>\n
$$\\begin{aligned}
\n\\min_{z} & \\quad \\frac{1}{2}z^TPz + q^Tz \\\\
\ns.t. & \\quad Gz \\leq h
\n\\end{aligned}$$<\/p>\n
3*. \u62c9\u683c\u6717\u65e5\u51fd\u6570\u8f6c\u6807\u51c6\u4e8c\u6b21\u89c4\u5212\u8fc7\u7a0b\u63a8\u5bfc<\/h2>\n1. \u539f\u59cb\u4f18\u5316\u95ee\u9898<\/h3>\n
\u9996\u5148\u5199\u51fa\u539f\u59cb\u95ee\u9898\uff1a<\/p>\n
$$\\begin{aligned}
\n\\min_{x,v} & \\quad \\frac{1}{2}||x - y||_2^2 + \\lambda\\sum_i v_i \\\\
\ns.t. & \\quad -v \\leq Dx \\leq v
\n\\end{aligned}$$<\/p>\n
2. \u6784\u5efa\u62c9\u683c\u6717\u65e5\u51fd\u6570<\/h3>\n
\u5c06\u4e0d\u7b49\u5f0f\u7ea6\u675f\u6539\u5199\u4e3a\uff1a<\/p>\n
$$Dx - v \\leq 0 \\text{ \u548c } -Dx - v \\leq 0$$<\/p>\n
\u5f15\u5165\u62c9\u683c\u6717\u65e5\u4e58\u5b50$\\mu_1, \\mu_2 \\geq 0$\uff0c\u5f97\u5230\u62c9\u683c\u6717\u65e5\u51fd\u6570\uff1a<\/p>\n
$$L(x,v,\\mu_1,\\mu_2) = \\frac{1}{2}||x - y||_2^2 + \\lambda\\sum_i v_i + \\mu_1^T(Dx - v) + \\mu_2^T(-Dx - v)$$<\/p>\n
3. \u6700\u4f18\u6027\u6761\u4ef6<\/h3>\n3.1 \u5bf9 x \u6c42\u5bfc\uff1a<\/h4>\n
$$\\frac{\\partial L}{\\partial x} = (x - y) + D^T(\\mu_1 - \\mu_2) = 0$$<\/p>\n
\u6574\u7406\u5f97\uff1a<\/p>\n
$$x = y - D^T(\\mu_1 - \\mu_2)$$<\/p>\n
3.2 \u5bf9 v \u6c42\u5bfc\uff1a<\/h4>\n
$$\\frac{\\partial L}{\\partial v} = \\lambda\\mathbf{1} - \\mu_1 - \\mu_2 = 0$$<\/p>\n
\u5f97\u5230\u7ea6\u675f\uff1a<\/p>\n
$$\\mu_1 + \\mu_2 = \\lambda\\mathbf{1}$$<\/p>\n
4. \u53d8\u91cf\u66ff\u6362\u4e0e\u7ea6\u675f\u8f6c\u5316<\/h3>\n
\u5b9a\u4e49\u65b0\u53d8\u91cf\uff1a<\/p>\n
$$z = \\mu_1 - \\mu_2$$<\/p>\n
\u7ed3\u5408$\\mu_1 + \\mu_2 = \\lambda\\mathbf{1}$\uff0c\u89e3\u51fa\uff1a<\/p>\n
$$\\mu_1 = \\frac{\\lambda\\mathbf{1} + z}{2}, \\quad \\mu_2 = \\frac{\\lambda\\mathbf{1} - z}{2}$$<\/p>\n
\u7531\u4e8e$\\mu_1, \\mu_2 \\geq 0$\uff0c\u5f97\u5230\uff1a<\/p>\n
$$|z_i| \\leq \\lambda$$<\/p>\n
5. \u76ee\u6807\u51fd\u6570\u8f6c\u5316<\/h3>\n
\u5c06$x = y - D^Tz$\u4ee3\u5165\u62c9\u683c\u6717\u65e5\u51fd\u6570\u5e76\u6574\u7406\uff1a<\/p>\n
5.1 \u5e73\u65b9\u9879\uff1a<\/h4>\n
$$\\frac{1}{2}||x - y||_2^2 = \\frac{1}{2}||D^Tz||_2^2 = \\frac{1}{2}z^TDD^Tz$$<\/p>\n
5.2 \u7ea6\u675f\u9879\uff1a<\/h4>\n
$$\\mu_1^T(Dx-v) + \\mu_2^T(-Dx-v) = z^TDy - z^TDD^Tz - \\lambda\\sum_i v_i$$<\/p>\n
5.3 \u5408\u5e76\u6240\u6709\u9879\uff1a<\/h4>\n
$$\\frac{1}{2}z^TDD^Tz + z^TDy - z^TDD^Tz = \\frac{1}{2}z^TDD^Tz - (-Dy)^Tz$$<\/p>\n
6. \u6700\u7ec8\u7684\u6807\u51c6\u4e8c\u6b21\u89c4\u5212\u5f62\u5f0f<\/h3>\n
$$\\begin{aligned}
\n\\min_z & \\quad \\frac{1}{2}z^T(DD^T)z + (-Dy)^Tz \\\\
\ns.t. & \\quad |z_i| \\leq \\lambda
\n\\end{aligned}$$<\/p>\n
\u8f6c\u6362\u4e3a\u6807\u51c6\u5f62\u5f0f\uff1a<\/p>\n
$$\\begin{aligned}
\n\\min_z & \\quad \\frac{1}{2}z^TPz + q^Tz \\\\
\ns.t. & \\quad Gz \\leq h
\n\\end{aligned}$$<\/p>\n
\u5176\u4e2d\uff1a<\/p>\n
- \n
- $P = DD^T$<\/li>\n
- $q = -Dy$<\/li>\n
- $G = \\begin{bmatrix} I \\\\ -I \\end{bmatrix}$<\/li>\n
- $h = \\lambda\\begin{bmatrix} \\mathbf{1} \\\\ \\mathbf{1} \\end{bmatrix}$<\/li>\n<\/ul>\n
7. \u7269\u7406\u610f\u4e49\u89e3\u91ca<\/h3>\n
\u8fd9\u4e2a\u8f6c\u5316\u7684\u5173\u952e\u70b9\u5728\u4e8e\uff1a<\/p>\n
- \n
- \n
\u53d8\u91cf\u66ff\u6362<\/strong>\uff1a\u4ece\u539f\u59cb\u7684 $(x,v)$ \u8f6c\u5316\u4e3a\u5355\u4e00\u53d8\u91cf $z$<\/p>\n<\/li>\n
- \n
z \u7684\u610f\u4e49<\/strong>\uff1a\u4ee3\u8868\u4fe1\u53f7\u5728\u5404\u4f4d\u7f6e\u7684\u4fee\u6b63\u5f3a\u5ea6<\/p>\n<\/li>\n
- \n
\u7ea6\u675f\u7b80\u5316<\/strong>\uff1a\u539f\u672c\u7684\u4e0d\u7b49\u5f0f\u7ea6\u675f\u8f6c\u5316\u4e3a\u5bf9 z \u7684\u8303\u6570\u7ea6\u675f<\/p>\n<\/li>\n
- \n
\u76ee\u6807\u51fd\u6570<\/strong>\uff1a<\/p>\n
- \n
- \u4e8c\u6b21\u9879 $\\frac{1}{2}z^T(DD^T)z$ \u5ea6\u91cf\u4e86\u8d8b\u52bf\u7684"\u4e0d\u5e73\u6ed1\u7a0b\u5ea6"<\/li>\n
- \u4e00\u6b21\u9879 $(-Dy)^Tz$ \u5c06\u539f\u59cb\u4fe1\u53f7\u4fe1\u606f\u5f15\u5165\u4f18\u5316\u8fc7\u7a0b<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n
\u8fd9\u79cd\u8f6c\u5316\u4f7f\u5f97\uff1a<\/p>\n
- \n
- \u95ee\u9898\u53d8\u5f97\u66f4\u5bb9\u6613\u6c42\u89e3\uff08\u6807\u51c6\u4e8c\u6b21\u89c4\u5212\uff09<\/li>\n
- \u4fdd\u6301\u4e86\u539f\u95ee\u9898\u7684\u6838\u5fc3\u7279\u5f81\uff08\u5e73\u6ed1\u6027\u548c\u6570\u636e\u4fdd\u771f\u5ea6\u7684\u5e73\u8861\uff09<\/li>\n
- \u63d0\u4f9b\u4e86\u6e05\u6670\u7684\u7269\u7406\u89e3\u91ca<\/li>\n<\/ul>\n
\u901a\u8fc7\u8fd9\u4e2a\u63a8\u5bfc\u8fc7\u7a0b\uff0c\u6211\u4eec\u53ef\u4ee5\u770b\u5230 L1 \u8d8b\u52bf\u6ee4\u6ce2\u7684\u4f18\u96c5\u4e4b\u5904\uff1a\u5b83\u5c06\u4e00\u4e2a\u770b\u4f3c\u590d\u6742\u7684\u975e\u5149\u6ed1\u4f18\u5316\u95ee\u9898\u8f6c\u5316\u4e3a\u4e86\u4e00\u4e2a\u6807\u51c6\u7684\u51f8\u4f18\u5316\u95ee\u9898\uff0c\u800c\u4e14\u4fdd\u6301\u4e86\u539f\u95ee\u9898\u7684\u6838\u5fc3\u7279\u5f81\u3002<\/p>\n
4. \u7b97\u6cd5\u5b9e\u73b0<\/h2>\n
4.1 \u6838\u5fc3\u4ee3\u7801\u5b9e\u73b0<\/h3>\n
from cvxopt import matrix, solvers, spmatrix\nimport numpy as np\n\ndef D_matrix(size):\n """\n \u6784\u5efa\u4e8c\u9636\u79bb\u6563\u5dee\u5206\u77e9\u9635\uff08\u4e8c\u9636\u5bfc\u6570\u77e9\u9635\uff09\u7684\u7a00\u758f\u77e9\u9635\u8868\u793a\n \n \u53c2\u6570:\n size (int): \u539f\u59cb\u4fe1\u53f7\u7684\u957f\u5ea6\n \n \u8fd4\u56de:\n cvxopt.spmatrix: \u7a00\u758f\u77e9\u9635\u683c\u5f0f\u7684\u4e8c\u9636\u5bfc\u6570\u77e9\u9635\n """\n temp = size - 2\n value = [1, -2, 1] * temp\n r_idx = [i for i in range(temp) for _ in range(3)]\n c_idx = [i + j for i in range(temp) for j in range(3)]\n return spmatrix(value, r_idx, c_idx)\n\ndef l1_trend_filter(signal, regularizer):\n """\n L1\u8d8b\u52bf\u6ee4\u6ce2\u7b97\u6cd5\u5b9e\u73b0\n \n \u4f18\u5316\u95ee\u9898:\n minimize (1\/2)||x - y||\u2082\u00b2 + \u03bb||Dx||\u2081\n \n \u8f6c\u5316\u4e3a\u6807\u51c6\u4e8c\u6b21\u89c4\u5212:\n minimize (1\/2)z^T(DD^T)z + (-Dy)^Tz\n subject to |z_i| \u2264 \u03bb\n \n \u6807\u51c6\u5f62\u5f0f:\n minimize (1\/2)z^TPz + q^Tz\n subject to Gz \u2264 h\n \n \u5176\u4e2d:\n P = DD^T\n q = -Dy\n G = [I; -I] # I \u4e3a\u5355\u4f4d\u77e9\u9635\n h = [\u03bb; \u03bb] # \u03bb \u4e3a\u6b63\u5219\u5316\u53c2\u6570\n \n \u53c2\u6570:\n signal (np.ndarray): \u8f93\u5165\u4fe1\u53f7, shape (n,1)\n regularizer (float): \u6b63\u5219\u5316\u53c2\u6570 \u03bb\n \n \u8fd4\u56de:\n trend (np.ndarray): \u63d0\u53d6\u7684\u4fe1\u53f7\u8d8b\u52bf\n """\n\n n = len(signal)\n\n # \u6784\u5efa\u4e8c\u9636\u5dee\u5206\u77e9\u9635\n D = D_matrix(n)\n # \u6784\u5efa\u4e8c\u6b21\u89c4\u5212\u7684\u4e8c\u6b21\u9879\u7cfb\u6570\u77e9\u9635\n P = D * D.T\n # \u6784\u5efa\u4e00\u6b21\u9879\n q = -D * signal\n \n # \u6784\u5efa\u4e0d\u7b49\u5f0f\u7ea6\u675f\u77e9\u9635G\u548c\u5411\u91cfh\n temp = n - 2\n G = spmatrix([], [], [], (2*temp, temp))\n G[:temp, :temp] = spmatrix(1.0, range(temp), range(temp))\n G[temp:, :temp] = -G[:temp, :temp]\n h = matrix(regularizer, (2*temp, 1), tc='d')\n \n # \u6c42\u89e3\u4e8c\u6b21\u89c4\u5212\u95ee\u9898\n result = solvers.qp(P, q, G, h)\n # \u91cd\u6784\u8d8b\u52bf\n trend = signal - D.T * result['x'] \n return trend\n<\/code><\/pre>\n
- \n
- \n
![\"image\"](\"http:\/\/kodo.cyasylum.top\/siyuan\/image-20241027162907-xlefj29.png\")
\u200b<\/p>\n