数据科学导论

1. 数据科学核心方法

• Sparse learning（稀疏学习）：用于信号处理、压缩感知，擅长小样本场景，核心是 “点积等价” 下的稀疏表示。
• Kernel learning（核学习）：通过核方法将数据映射到高维特征空间，解决非线性问题。
• Classification（分类）：结合概率统计与经验回归，将样本映射到特征空间后分类。
• Deep learning（深度学习，非线性模型）：构建复杂非线性模型，但存在 “难优化、难训练” 的问题，需关注经验风险的估计与控制。

2. 傅里叶变换与效率

• FFT（快速傅里叶变换）：是 DFT（离散傅里叶变换）的高效实现，时间复杂度为 O(NlogN)，大幅提升频域分析效率。

3. 压缩感知（Compressed Sensing）

核心是**从少量测量中恢复高维稀疏信号**，典型优化问题：

• 带约束的 ℓ1 最小化：min∥x∥1，满足 Ψx=y（Ψ 为测量矩阵，y 为测量值）；
• 正则化形式：∥x∥2+λ∥Ψx−y∥（平衡稀疏性与测量误差）；
• 实现思路：通过 ** 奇异值分解（SVD）** 提取前 K 个重要奇异值，只保留关键信息实现 “压缩”。

4. 应用示例（Netflix 类问题）

对高维向量 x∈Rd，通过测量矩阵 Ψ∈Rm×d 得到低维测量 y∈Rm（满足 n≪d，即测量数远少于维度），类似 “随机照相机” 的采样方式，从少量测量中恢复真实向量 x，即求解 Ψx=y。

优化与机器学习笔记

记录了稀疏优化、推荐系统及深度学习的相关思路与模型：

1. 稀疏优化与测量误差

1. 压缩感知的优化模型

压缩感知通过**稀疏性假设**恢复信号，核心优化模型为：

• 带噪声观测：min∥x∥1，约束 y=Ψx+ε（ε 为噪声，Ψ 为感知矩阵）；
• 无约束正则化形式：min∥x∥1+λ∥y−Ψx∥22（λ 为正则化参数，平衡稀疏性与拟合度）。

求解无约束形式时，可通过**Lagrange 乘数法**构造增广目标：

minx,y∥x∥1+λ∥y−Ψx∥22,

再结合对偶问题（如交换优化顺序、利用凸共轭）分析最优性条件。

针对含测量误差的信号恢复问题 y=Ψx+误差，典型的正则化优化目标为：

min∥x∥1+∥y−Ψx∥22+λ∥x∥2

（结合 ℓ1 稀疏性、ℓ2 测量误差与 ℓ2 正则化，平衡稀疏与光滑性）；

若目标函数非光滑（如含 ℓ1 范数），需用**次梯度方法**求解。

2. 推荐系统与矩阵优化

推荐系统常涉及矩阵范数与秩的优化，例如：

min∥X∥p,q,满足 P2(X)=P2(M)

（∥⋅∥p,q 为矩阵的混合范数，P2(⋅) 关联核范数 / 秩，通过约束矩阵的 “谱性质” 实现推荐逻辑）。

提问：为什么要用核范数这个特殊的范数来代替？核范数也就是所有奇异值的和为什么就是一个最佳逼近？

3. 深度神经网络的应用

深度神经网络是解决复杂非线性问题的核心方法之一，尤其在 “高维测量与低维向量映射” 场景（如 b>>n 时，Ψ 为测量矩阵，x 为待恢复向量）中，能通过多层非线性变换更好地拟合映射关系。

深度学习分类模型

2. 损失函数的期望与经验形式

在机器学习（如分类问题）中，常用**对数损失函数**：

• 期望形式（总体损失）：

L(f)=E(x,y)[log(1+e−yf(x))]

（

(x,y)

为样本与标签对，

y∈{−1,1}

，

f(x)

为模型预测函数）；

• 经验形式（样本平均损失）：

L^(f)=n1∑i=1nlog(1+e−yif(xi))

（用有限样本近似总体期望，需分析

f^

与最优函数

f∗

的范数收敛性

∥f∗−f^∥→?

）。

快速傅里叶变换

2. 快速傅里叶变换（FFT）的递归推导

快速傅里叶变换用于高效计算离散傅里叶变换（DFT），核心是**分治策略**（将大问题拆分为小问题）：

• DFT 定义：对序列 x0,x1,…,xn−1，其 DFT 为

Xk=∑i=0n−1e−2πinkixi(k=0,1,…,n−1),

其中 e−2πin1 为旋转因子（记为 wn）。

• 奇偶拆分：将序列按下标奇偶拆分为两个子序列，DFT 可表示为：

Xk=∑i=02n−1wn2kix2i+wnk∑i=02n−1wn2kix2i+1.

利用旋转因子性质 wn2k=w2nk，可将问题拆分为两个长度为 2n 的 DFT 计算。

• 时间复杂度递归式：设 T(n) 为计算 n 点 DFT 的时间，分治后满足

T(n)=2T(2n)+O(n),

解得 T(n)=O(nlogn)（远优于直接计算的 O(n2)）