(線性代數) 影像壓縮和工業系

 

Source by Frank Cleary

看得出來兩張圖片的差別？

學習數學的四個層次：(3) 在許多行業的應用

學習數學的四個層次：(0) 如何學數學，(1) 代表具備基礎的知識與能力，(2) 邏輯推理和抽象思考的能力，(3) 在許多行業的應用，(4) 純粹滿足好奇心或求知慾。

2015/12/1 初稿，持續更新中。

一般性說明

• 數學是科學之母，科學則是工業的基礎，所以大學工學院的數理化課程總學分超過 1/3。可以參考如何選填大學志願。
• 應用在不同的領域 (理工商醫農、教育)，如財務工程、設計電腦、貨物產銷、工程師、使用統計學分析學習成效等等。
• 抽象的模式與思考的方式，適用於現在與未來的應用，以微分為例，物理學的距離微分是速度，經濟學中成本的微分是邊際成本，電子學的電荷微分是電流。也就是說，可以使用函數表示任何待解的問題，函數的微分便可以研究其變化和極值的情況，例如機器學習中，超參數 (hyperparameter) 的學習 。
• 基本的原則變動不大，微積分、機率和統計學、和線性代數已經有 200 年以上的歷史，可幫助未來的自我學習。許多人說學校學的東西，畢業後立即過時或沒用，我覺得很疑惑。大學只是基礎教育，必須不斷地學習新的東西，以因應產業和職務的變化；最近熱門的大數據 (big data) 和人工智慧 (artificial intelligence)，其數學基礎正是這些課程。
  

Sparse PCA: A New Scalable Estimator Based On Integer Programming

Kayhan Behdin and Rahul Mazumder, Sparse PCA: A New Scalable Estimator Based On Integer Programming, arXiv:2109.11142v2, 2021. (Julia ahd Gurobi code)

We consider the Sparse Principal Component Analysis (SPCA) problem under the well-known spiked covariance model. Recent work has shown that the SPCA problem can be reformulated as a Mixed Integer Program (MIP) and can be solved to global optimality, leading to estimators that are known to enjoy optimal statistical properties. However, current MIP algorithms for SPCA are unable to scale beyond instances with a thousand features or so. In this paper, we propose a new estimator for SPCA which can be formulated as a MIP. Different from earlier work, we make use of the underlying spiked covariance model and properties of the multivariate Gaussian distribution to arrive at our estimator. We establish statistical guarantees for our proposed estimator in terms of estimation error and support recovery. We propose a custom algorithm to solve the MIP which is significantly more scalable than off-the-shelf solvers; and demonstrate that our approach can be much more computationally attractive compared to earlier exact MIP-based approaches for the SPCA problem. Our numerical experiments on synthetic and real datasets show that our algorithms can address problems with up to 20000 features in minutes; and generally result in favorable statistical properties compared to existing popular approaches for SPCA.

The Art of Linear Algebra

Kenji Hiranabe, Graphic notes on Gilbert Strang's "Linear Algebra for Everyone"

I tried intuitive visualizations of important concepts introduced in "Linear Algebra for Everyone".

Discovering faster matrix multiplication algorithms with reinforcement learning

Fawzi, A., Balog, M., Huang, A. et al. Discovering faster matrix multiplication algorithms with reinforcement learning. Nature 610, 47–53 (2022). https://doi.org/10.1038/s41586-022-05172-4. (data and code)

Improving the efficiency of algorithms for fundamental computations can have a widespread impact, as it can affect the overall speed of a large amount of computations. Matrix multiplication is one such primitive task, occurring in many systems—from neural networks to scientific computing routines. The automatic discovery of algorithms using machine learning offers the prospect of reaching beyond human intuition and outperforming the current best human-designed algorithms. However, automating the algorithm discovery procedure is intricate, as the space of possible algorithms is enormous. Here we report a deep reinforcement learning approach based on AlphaZero for discovering efficient and provably correct algorithms for the multiplication of arbitrary matrices. Our agent, AlphaTensor, is trained to play a single-player game where the objective is finding tensor decompositions within a finite factor space. AlphaTensor discovered algorithms that outperform the state-of-the-art complexity for many matrix sizes. Particularly relevant is the case of 4 × 4 matrices in a finite field, where AlphaTensor’s algorithm improves on Strassen’s two-level algorithm for the first time, to our knowledge, since its discovery 50 years ago. We further showcase the flexibility of AlphaTensor through different use-cases: algorithms with state-of-the-art complexity for structured matrix multiplication and improved practical efficiency by optimizing matrix multiplication for runtime on specific hardware. Our results highlight AlphaTensor’s ability to accelerate the process of algorithmic discovery on a range of problems, and to optimize for different criteria.

ACM Turing Award Honors Jack J. Dongarra

ACM, ACM Turing Award Honors Jack J. Dongarra for Pioneering Concepts and Methods Which Have Resulted in World-Changing Computations, March 30, 2022.

ACM, the Association for Computing Machinery, today named Jack J. Dongarra recipient of the 2021 ACM A.M. Turing Award for pioneering contributions to numerical algorithms and libraries that enabled high performance computational software to keep pace with exponential hardware improvements for over four decades. Dongarra is a University Distinguished Professor of Computer Science in the Electrical Engineering and Computer Science Department at the University of Tennessee. He also holds appointments with Oak Ridge National Laboratory and the University of Manchester.

Efficient method for training deep networks with unitary matrices

Bobak Kiani, Randall Balestriero, Yann Lecun, and Seth Lloyd,  projUNN: efficient method for training deep networks with unitary matrices, arXiv:2203.05483v2.

In learning with recurrent or very deep feed-forward networks, employing unitary matrices in each layer can be very effective at maintaining long-range stability. However, restricting network parameters to be unitary typically comes at the cost of expensive parameterizations or increased training runtime. We propose instead an efficient method based on rank-k updates -- or their rank-k approximation -- that maintains performance at a nearly optimal training runtime. We introduce two variants of this method, named Direct (projUNN-D) and Tangent (projUNN-T) projected Unitary Neural Networks, that can parameterize full N-dimensional unitary or orthogonal matrices with a training runtime scaling as O(kN^2). Our method either projects low-rank gradients onto the closest unitary matrix (projUNN-T) or transports unitary matrices in the direction of the low-rank gradient (projUNN-D). Even in the fastest setting (k=1), projUNN is able to train a model's unitary parameters to reach comparable performances against baseline implementations. By integrating our projUNN algorithm into both recurrent and convolutional neural networks, our models can closely match or exceed benchmarked results from state-of-the-art algorithms.

Minimum-Distortion Embedding

Akshay Agrawal, Alnur Ali and Stephen Boyd (2021), "Minimum-Distortion Embedding", Foundations and Trends® in Machine Learning: Vol. 14: No. 3, pp 211-378. http://dx.doi.org/10.1561/2200000090. 

We consider the vector embedding problem. We are given a finite set of items, with the goal of assigning a representative vector to each one, possibly under some constraints (such as the collection of vectors being standardized, i.e., have zero mean and unit covariance). We are given data indicating that some pairs of items are similar, and optionally, some other pairs are dissimilar. For pairs of similar items, we want the corresponding vectors to be near each other, and for dissimilar pairs, we want the corresponding vectors to not be near each other, measured in Euclidean distance. We formalize this by introducing distortion functions, defined for some pairs of the items. Our goal is to choose an embedding that minimizes the total distortion, subject to the constraints. We call this the minimum-distortion embedding (MDE) problem.

This monograph is accompanied by an open-source Python package, PyMDE, for approximately solving MDE problems. Users can select from a library of distortion functions and constraints or specify custom ones, making it easy to rapidly experiment with different embeddings. Because our algorithm is scalable, and because PyMDE can exploit GPUs, our software scales to data sets with millions of items and tens of millions of distortion functions. Additionally, PyMDE is competitive in runtime with specialized implementations of specific embedding methods. To demonstrate our method, we compute embeddings for several real-world data sets, including images, an academic co-author network, US county demographic data, and single-cell mRNA transcriptomes.

Linear Algebra, Signal Processing, and Wavelets - A Unified Approach

Øyvind Ryan, Linear Algebra, Signal Processing, and Wavelets - A Unified Approach, Python Version, Springer, 2019.  (code, Python)

1 Sound and Fourier Series

2 Digital Sound and Discrete Fourier Analysis

3 Discrete Time Filters

4 Motivation for Wavelets and Some Simple Examples

5 The Filter Representation of Wavelets

6 Constructing Interesting Wavelets

7 The Polyphase Representation of Filter Bank Transforms

8 Digital Images

9 Using Tensor Products to Apply Wavelets to Images

Appendix Basic Linear Algebra 

Numerical Python

Robert Johansson, Numerical Python: Scientific Computing and Data Science Applications with Numpy, SciPy and Matplotlib, Apress, 2019. (code)

 Leverage the numerical and mathematical modules in Python and its standard library as well as popular open source numerical Python packages like NumPy, SciPy, FiPy, matplotlib and more. This fully revised edition, updated with the latest details of each package and changes to Jupyter projects, demonstrates how to numerically compute solutions and mathematically model applications in big data, cloud computing, financial engineering, business management and more. 

Numerical Algorithms: Methods for Computer Vision, Machine Learning, and Graphics

Justin Solomon, Numerical Algorithms: Methods for Computer Vision, Machine Learning, and Graphics,  1st Edition, A K Peters/CRC Press, 2015. (pdf)

Numerical Algorithms: Methods for Computer Vision, Machine Learning, and Graphics presents a new approach to numerical analysis for modern computer scientists. Using examples from a broad base of computational tasks, including data processing, computational photography, and animation, the textbook introduces numerical modeling and algorithmic design from a practical standpoint and provides insight into the theoretical tools needed to support these skills.

The book covers a wide range of topics—from numerical linear algebra to optimization and differential equations—focusing on real-world motivation and unifying themes. It incorporates cases from computer science research and practice, accompanied by highlights from in-depth literature on each subtopic. Comprehensive end-of-chapter exercises encourage critical thinking and build students’ intuition while introducing extensions of the basic material.

The text is designed for advanced undergraduate and beginning graduate students in computer science and related fields with experience in calculus and linear algebra. For students with a background in discrete mathematics, the book includes some reminders of relevant continuous mathematical background.

Probabilistic Machine Learning

 "Probabilistic Machine Learning" - a book series by Kevin Murphy

Kevin Patrick Murphy, Probabilistic Machine Learning: An Introduction, MIT Press, 2021. (Python codes)

新的版本，作者花了很多時間整理。以第一部分的數學基礎為例，使用機器學習說明相關的概念。也納入時事，例如 2.3.1 節的 Testing for COVID-19。 

EE104/CME107 Introduction to Machine Learning

Sanjay Lall, EE104/CME107: Introduction to Machine Learning, Stanford University, Spring Quarter, 2021. (quarter: 10 weeks, Julia, YouTube)

Introduction to machine learning. Formulation of supervised and unsupervised learning problems. Regression and classification. Data standardization and feature engineering. Loss function selection and its effect on learning. Regularization and its role in controlling complexity. Validation and overfitting. Robustness to outliers. Simple numerical implementation. Experiments on data from a wide variety of engineering and other disciplines.

共同作者為 S. Boyd，兩位教授的寫作非常清楚，推薦。 

Machine Learning Under a Modern Optimization Lens

Dimitris Bertsimas and Jack Dunn, Machine Learning Under a Modern Optimization Lens, Dynamic Ideas LLC, 2019.

The book provides an original treatment of machine learning (ML) using convex, robust and mixed integer optimization that leads to solutions to central ML problems at large scale that can be found in seconds/minutes, can be certified to be optimal in minutes/hours, and outperform classical heuristic approaches in out-of-sample experiments.

(高中) 數學與資訊工程

馬來西亞的學校提案，準備今年 5 月，開授相關線上演講，以便吸引高中生就讀資訊相關科系。去年12月中開校內協調會的時候，學校長官指派我，負責「數學與資訊工程 」。 月底到了，忙著提科技部計畫和撰寫研究的程式，但是，各種點子不斷地進入我的腦袋裡，只好趕緊把它寫下來，不然半夜進入我的夢鄉，擾人清夢。花了兩天，寫下初稿；最近又多次修正，前後花了不下 20 小時，決定提前定稿 ，以便改作其他教學和研究事務。

後來想一想， 既然這是一個有意義的工作，就準備把他錄成影片，並上傳 YouTube，以幫助有需要的年輕人。追求新知並傳授給學生，一直是我當老師快樂的泉源。

歡迎指正和提供寶貴意見。(pdf in 1) (pdf in 4，如果需要列印， 請雙面列印此版本，環保救地球)

初稿 2021/1/15。

Matrix Multiplication Inches Closer to Mythic Goal

Kevin Hartnett, Matrix Multiplication Inches Closer to Mythic Goal, Quanta Magazine, March 23, 2021.

“Exponent two” refers to the ideal speed — in terms of number of steps required — of performing one of the most fundamental operations in math: matrix multiplication. If exponent two is achievable, then it’s possible to carry out matrix multiplication as fast as physically possible. If it’s not, then we’re stuck in a world misfit to our dreams.

咖啡廳裡親子的對話

 有一天，在咖啡廳裡工作，聽到隔壁一對父母在教小孩。

大概的情況是，小孩子的作業訂正有問題，媽媽非常地生氣，期間也說明別人是如何如何，為什麼你都做不好？小孩子低聲啜泣，對媽媽的話，也不太敢反駁。爸爸則是說，我們不是和乞丐比較，唸書是要幫你找到好工作、賺錢 。後來，我和小孩剛好都離座，在走道上，我仔細地看了小孩一眼，一看就是一個乖巧、懂事的小孩子。回座後，夫妻開始有不同的意見。前後超過一個小時。

當下有非常高的衝動，想要和父母講一下。但是，我怕被白眼，所以還是忍了下來。

A First Course in Random Matrix Theory

Marc Potters, A First Course in Random Matrix Theory (for Physicists, Engineers and Data Scientists), Cambridge University Press, 2020.

The real world is perceived and broken down as data, models and algorithms in the eyes of physicists and engineers. Data is noisy by nature and classical statistical tools have so far been successful in dealing with relatively smaller levels of randomness. The recent emergence of Big Data and the required computing power to analyse them have rendered classical tools outdated and insufficient. Tools such as random matrix theory and the study of large sample covariance matrices can efficiently process these big data sets and help make sense of modern, deep learning algorithms. Presenting an introductory calculus course for random matrices, the book focusses on modern concepts in matrix theory, generalising the standard concept of probabilistic independence to non-commuting random variables. Concretely worked out examples and applications to financial engineering and portfolio construction make this unique book an essential tool for physicists, engineers, data analysts, and economists.

Mathematics for Machine Learning

Marc Peter Deisenroth, A. Aldo Faisal, and Cheng Soon Ong, Mathematics for Machine Learning, Cambridge University Press, 2020. (pdf)

The book assumes the reader to have mathematical knowledge commonly covered in high school mathematics and physics. For example, the reader should have seen derivatives and integrals before, and geometric vectors in two or three dimensions. Starting from there, we generalize these concepts. Therefore, the target audience of the book includes undergraduate university students, evening learners and learners participating in online machine learning courses.

Linear Algebra and Optimization for Machine Learning: A Textbook

Charu C. Aggarwal, Linear Algebra and Optimization for Machine Learning: A Textbook, Springer, 1st ed, 2020.

This textbook introduces linear algebra and optimization in the context of machine learning. Examples and exercises are provided throughout the book. A solution manual for the exercises at the end of each chapter is available to teaching instructors. This textbook targets graduate level students and professors in computer science, mathematics and data science. Advanced undergraduate students can also use this textbook. The chapters for this textbook are organized as follows: