{ "cells": [ { "cell_type": "raw", "metadata": {}, "source": [ "---\n", "title: Biostat 216 Homework 2\n", "subtitle: 'Due Oct 13 @ 11:59pm'\n", "format:\n", " html:\n", " theme: cosmo\n", " embed-resources: true\n", " number-sections: true\n", " toc: true\n", " toc-depth: 4\n", " toc-location: left\n", " code-fold: false\n", "---" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Submit a PDF (scanned/photographed from handwritten solutions, or converted from RMarkdown or Jupyter Notebook or Quarto) to Gradescope in BruinLearn. \n", "\n", "## Q1. Average and norm\n", "\n", "Use the Cauchy-Schwarz inequality to prove that\n", "$$\n", "- \\frac{1}{\\sqrt{n}} \\|\\mathbf{x}\\| \\le \\frac{1}{n} \\sum_{i=1}^n x_i \\le \\frac{1}{\\sqrt{n}} \\|\\mathbf{x}\\|\n", "$$\n", "for any $\\mathbf{x} \\in \\mathbb{R}^n$. In other words, $-\\operatorname{rms}(\\mathbf{x}) \\le \\operatorname{avg}(\\mathbf{x}) \\le \\operatorname{rms}(\\mathbf{x})$.\n", "\n", "What are the conditions on $\\mathbf{x}$ to have equality in the upper bound? When do we have equality in the lower bound?\n", "\n", "## Q2. AM-HM inequality\n", "\n", "Use the Cauchy-Schwartz inequality to prove that\n", "$$\n", "\\frac{1}{n} \\sum_{i=1}^n x_i \\ge \\left( \\frac{1}{n} \\sum_{i=1}^n \\frac{1}{x_i} \\right)^{-1}\n", "$$\n", "for any $\\mathbf{x} \\in \\mathbb{R}^n$ with positive entries $x_i$. \n", "\n", "The left hand side is called the arithmetic mean (AM) and the right hand side is called the harmonic mean (HM). You may wonder what can be a practical use of such a simple inequality. See this [paper](http://hua-zhou.github.io/media/pdf/LangeZhou14GP.pdf), which uses the AM-GM inequality to derive a class of optimization algorithms for geometric and signomial programming.\n", "\n", "## Q3. Sub-multiplicity for matrix norm\n", "\n", "Show the norm property \n", "$$\n", "\\|\\mathbf{A} \\mathbf{B}\\| \\le \\|\\mathbf{A}\\| \\|\\mathbf{B}\\|\n", "$$ \n", "for the Frobenius norm. Hint: Cauchy-Schwartz inequality.\n", "\n", "BV exercise 6.14 is a special case of this result.\n", "\n", "## Q4. $k$-means clustering\n", "\n", "Read BV Chapter 4.\n", "\n", "1. BV exercise 4.1.\n", "\n", "2. (Optional) Implement the $k$-means algorithm (BV Algorithm 4.1) and apply to the 60,000 MNIST training images with $k=20$. Can we reproduce the Figures 4.7-4.9 in BV textbook? For Julia users, you can start with the following code." ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "\u001b[32m\u001b[1m Activating\u001b[22m\u001b[39m project at `~/Documents/github.com/ucla-biostat-216/2023fall/hw/hw2`\n" ] } ], "source": [ "#| echo: false\n", "#| output: false\n", "\n", "using Pkg\n", "Pkg.activate(pwd())\n", "Pkg.instantiate()" ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(28, 28, 60000)" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "using MLDatasets\n", "\n", "# training images\n", "size(MNIST().features)" ] }, { "cell_type": "code", "execution_count": 23, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "784×60000 Matrix{Float32}:\n", " 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 … 0.0 0.0 0.0 0.0 0.0 0.0 0.0\n", " 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0\n", " 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0\n", " 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0\n", " 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0\n", " 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 … 0.0 0.0 0.0 0.0 0.0 0.0 0.0\n", " 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0\n", " 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0\n", " 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0\n", " 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0\n", " 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 … 0.0 0.0 0.0 0.0 0.0 0.0 0.0\n", " 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0\n", " 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0\n", " ⋮ ⋮ ⋱ ⋮ \n", " 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0\n", " 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0\n", " 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0\n", " 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 … 0.0 0.0 0.0 0.0 0.0 0.0 0.0\n", " 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0\n", " 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0\n", " 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0\n", " 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0\n", " 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 … 0.0 0.0 0.0 0.0 0.0 0.0 0.0\n", " 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0\n", " 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0\n", " 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0" ] }, "execution_count": 23, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# vec each image into a 784-vector\n", "X = reshape(MNIST().features, (28 * 28, 60000))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## BV exercises\n", "\n", "5.1, 5.2, 5.4, 5.6, 5.8, 5.9, 6.3, 6.11, 6.17, 6.21, 6.22" ] } ], "metadata": { "@webio": { "lastCommId": null, "lastKernelId": null }, "hide_input": false, "jupytext": { "formats": "ipynb,qmd" }, "kernelspec": { "display_name": "Julia 1.9.3", "language": "julia", "name": "julia-1.9" }, "language_info": { "file_extension": ".jl", "mimetype": "application/julia", "name": "julia", "version": "1.9.3" }, "toc": { "colors": { "hover_highlight": "#DAA520", "running_highlight": "#FF0000", "selected_highlight": "#FFD700" }, "moveMenuLeft": true, "nav_menu": { "height": "87px", "width": "252px" }, "navigate_menu": true, "number_sections": true, "sideBar": true, "skip_h1_title": true, "threshold": 4, "toc_cell": false, "toc_section_display": "block", "toc_window_display": false, "widenNotebook": false } }, "nbformat": 4, "nbformat_minor": 4 }