import%20marimo%0A%0A__generated_with%20%3D%20%220.24.0%22%0Aapp%20%3D%20marimo.App(width%3D%22medium%22)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20Sparse%20Dictionary%20Learning%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20import%20warnings%0A%20%20%20%20from%20pathlib%20import%20Path%0A%0A%20%20%20%20warnings.filterwarnings(%22ignore%22)%0A%0A%20%20%20%20import%20cvxpy%20as%20cp%0A%20%20%20%20import%20marimo%20as%20mo%0A%20%20%20%20import%20matplotlib.pyplot%20as%20plt%0A%20%20%20%20import%20numpy%20as%20np%0A%0A%20%20%20%20from%20dbcp%20import%20BiconvexProblem%0A%0A%20%20%20%20_example_directory%20%3D%20Path(__file__).resolve().parent%0A%20%20%20%20plt.style.use(_example_directory%20%2F%20%22zhlatex.mplstyle%22)%0A%20%20%20%20figure_directory%20%3D%20_example_directory%20%2F%20%22figures%22%0A%20%20%20%20figure_directory.mkdir(parents%3DTrue%2C%20exist_ok%3DTrue)%0A%0A%20%20%20%20np.random.seed(10015)%0A%20%20%20%20return%20BiconvexProblem%2C%20cp%2C%20figure_directory%2C%20mo%2C%20np%2C%20plt%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Introduction%0A%0A%20%20%20%20We%20consider%20the%20sparse%20dictionary%20learning%20problem%2C%20which%20aims%20to%20find%20a%20dictionary%20matrix%0A%20%20%20%20%24D%20%5Cin%20%5Cmathbf%7BR%7D%5E%7Bm%20%5Ctimes%20k%7D%24%20and%20a%20sparse%20code%20matrix%20%24X%20%5Cin%20%5Cmathbf%7BR%7D%5E%7Bk%20%5Ctimes%20n%7D%24%2C%20such%20that%20the%20data%0A%20%20%20%20matrix%20%24Y%20%5Cin%20%5Cmathbf%7BR%7D%5E%7Bm%20%5Ctimes%20n%7D%24%20can%20be%20well%20approximated%20by%20their%20product%20%24DX%24%2C%20while%20the%20matrix%20%24X%24%0A%20%20%20%20is%20sparse%20and%20the%20matrix%20%24D%24%20has%20bounded%20Frobenius%20norm.%0A%20%20%20%20The%20dictionary%20learning%20problem%20can%20be%20formulated%20as%20the%20following%20biconvex%20optimization%20problem%3A%0A%0A%20%20%20%20%5C%5B%0A%20%20%20%20%20%20%20%20%5Cbegin%7Barray%7D%7Bll%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20%5Ctext%7Bminimize%7D%20%26%20%7B%5C%7CDX%20-%20Y%5C%7C%7D_F%5E2%20%2B%20%5Calpha%20%7B%5C%7CX%5C%7C%7D_1%5C%5C%0A%20%20%20%20%20%20%20%20%20%20%20%20%5Ctext%7Bsubject%20to%7D%20%26%20%7B%5C%7CD%5C%7C%7D_F%20%5Cleq%20%5Cbeta%0A%20%20%20%20%20%20%20%20%5Cend%7Barray%7D%0A%20%20%20%20%5C%5D%0A%0A%20%20%20%20with%20variables%20%24D%24%20and%20%24X%24%2C%20where%20%24%5Calpha%20%3E%200%24%20is%20the%20sparsity%20regularization%20parameter%2C%20and%20%24%5Cbeta%20%3E%200%24%0A%20%20%20%20is%20the%20bound%20on%20the%20Frobenius%20norm%20of%20the%20dictionary%20matrix.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Generate%20problem%20data%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(np)%3A%0A%20%20%20%20m%20%3D%2010%0A%20%20%20%20n%20%3D%2020%0A%20%20%20%20k%20%3D%2020%0A%20%20%20%20beta%20%3D%201%0A%0A%20%20%20%20Y%20%3D%20np.random.randn(m%2C%20n)%0A%20%20%20%20return%20Y%2C%20beta%2C%20k%2C%20m%2C%20n%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Specify%20and%20solve%20the%20problem%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(BiconvexProblem%2C%20Y%2C%20beta%2C%20cp%2C%20k%2C%20m%2C%20n%2C%20np)%3A%0A%20%20%20%20D%20%3D%20cp.Variable((m%2C%20k))%0A%20%20%20%20X%20%3D%20cp.Variable((k%2C%20n))%0A%20%20%20%20alpha%20%3D%20cp.Parameter(nonneg%3DTrue)%0A%20%20%20%20obj%20%3D%20cp.Minimize(cp.sum_squares(D%20%40%20X%20-%20Y)%20%2B%20alpha%20*%20cp.norm1(X))%0A%20%20%20%20prob%20%3D%20BiconvexProblem(obj%2C%20%5BD%5D%2C%20%5BX%5D%2C%20%5Bcp.norm(D%2C%20%22fro%22)%20%3C%3D%20beta%5D)%0A%0A%20%20%20%20errs%20%3D%20%5B%5D%0A%20%20%20%20cards%20%3D%20%5B%5D%0A%20%20%20%20for%20_a%20in%20np.logspace(-5%2C%200%2C%2050)%3A%0A%20%20%20%20%20%20%20%20alpha.value%20%3D%20_a%0A%20%20%20%20%20%20%20%20D.value%20%3D%20None%0A%20%20%20%20%20%20%20%20X.value%20%3D%20None%0A%20%20%20%20%20%20%20%20prob.solve(cp.CLARABEL%2C%20abs_tol%3D1e-1)%0A%20%20%20%20%20%20%20%20errs.append(cp.norm(D%20%40%20X%20-%20Y%2C%20%22fro%22).value%20%2F%20cp.norm(Y%2C%20%22fro%22).value)%0A%20%20%20%20%20%20%20%20cards.append(cp.sum(cp.abs(X).value%20%3E%3D%201e-3).value)%0A%20%20%20%20return%20cards%2C%20errs%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Plot%20the%20results%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(cards%2C%20errs%2C%20figure_directory%2C%20plt)%3A%0A%20%20%20%20fig%2C%20axs%20%3D%20plt.subplots(1%2C%201%2C%20figsize%3D(5%2C%204))%0A%20%20%20%20axs.plot(cards%2C%20errs%2C%20marker%3D%22.%22%2C%20color%3D%22k%22)%0A%20%20%20%20axs.set_xlabel(r%22%24%5Cmathbf%7Bcard%7D%5C%2CX%24%22)%0A%20%20%20%20axs.set_ylabel(%22%24%7C%7CDX-Y%7C%7C_F%2F%7C%7CY%7C%7C_F%24%22)%0A%0A%20%20%20%20fig.tight_layout()%0A%20%20%20%20fig.savefig(figure_directory%20%2F%20%22dict_learning.pdf%22%2C%20bbox_inches%3D%22tight%22)%0A%20%20%20%20plt.show()%0A%20%20%20%20return%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A
09084eff31638a1d2dea907323682847