0329-Morphological component analysis on the sphere
Morphological component analysis on the sphere
The solution to this estimation problem will depend heavily on the available prior information. Of interest here is the case where one is given a priori a set a waveforms from which to select a good subset. This set may be a basis, a frame or several bases or frames grouped into a large redundant dictionary
数据集 y 可以在数据空间的任何完整基础上有一个精确表示，或在冗余过完备字典的情况下有几个这样的精确表示。然而，这些表示在数据建模或特征检测方面并不同等有趣。实际上，一个强有力的先验是偏好使用只需要少量波形的 y 表示，从而得到更简洁且可能更易于解释的数据表示。事实上，构建稀疏表示或近似是结构化数据处理的艺术：设计良好的检测、去噪、恢复和压缩算法依赖于良好字典和良好选择算法的可用性。实际上，从大字典中选择最小的波形子集，这些波形子集将线性组合以再现给定信号或图像的显著特征，是一个困难的组合问题。已经提出了几种追踪算法，可以帮助构建非常稀疏的分解，如贪婪匹配追踪（MP）（Mallat 和 Zhang 1993）算法，它通过在每次迭代中挑选与当前近似误差最相关的一个波形来细化信号近似。基追踪（BP）（Chen 等，1999）是一个全局程序，它通过解决线性规划问题寻找近似 $\hat y$ 到 y。
Further, experiments have clearly shown that the optimal number of iterations depends on the data.
$\ell_0 $ pseudo-norm
The $ \ell_0 $ pseudo-norm of a vector $ \mathbf{x} $ is a measure used in mathematics, particularly in the context of sparse solutions to optimization problems and signal processing. It is referred to as a pseudo-norm because it doesn't satisfy all the properties required to be a true norm, specifically the triangle inequality and homogeneity.
The $ \ell_0 $ pseudo-norm, denoted as $ | \mathbf{x} |_0 $, is defined as the number of non-zero entries in the vector $ \mathbf{x} $. In other words, it simply counts how many elements of $ \mathbf{x} $ are different from zero.
For example, if
then
because there are three non-zero elements in $ \mathbf{x} $.
In optimization problems, minimizing the $ \ell_0 $ pseudo-norm of a vector often leads to solutions that are sparse, meaning most of the vector's elements are zero. This is a desirable property in many applications like signal processing (for sparse signal recovery), machine learning (for feature selection), and compressed sensing.
However, minimizing the $ \ell_0 $ pseudo-norm is generally an NP-hard problem, which means it is computationally infeasible for large datasets or high-dimensional problems. As a result, many optimization techniques use convex relaxations or approximations, such as the $ \ell_1 $ norm (also known as the least absolute shrinkage and selection operator or LASSO), which is computationally more tractable and can still promote sparsity
$\ell_1$ norm
The $ \ell_1 $ sparsity measure, also known as the $ \ell_1 $ norm, is a mathematical concept used to quantify the sparsity of a vector in a way that is more tractable for computation compared to the $ \ell_0 $ pseudo-norm.
The $ \ell_1 $ norm of a vector $ \mathbf{x} $ is defined as the sum of the absolute values of its components. Mathematically, for a vector $ \mathbf{x} \in \mathbb{R}^n $, its $ \ell_1 $ norm is given by:
This measure is often used in optimization problems, particularly in the field of compressive sensing and sparse recovery, because it has been shown to be a good convex surrogate for the non-convex $ \ell_0 $ pseudo-norm. Minimizing the $ \ell_1 $ norm tends to promote sparsity in the vector $ \mathbf{x} $, causing many components of $ \mathbf{x} $ to become zero or close to zero, thus resulting in a sparse solution.
The use of the $ \ell_1 $ norm is advantageous because, unlike the $ \ell_0 $ pseudo-norm, it results in a convex optimization problem that can be solved efficiently even for large-scale problems. Algorithms such as the Least Absolute Shrinkage and Selection Operator (LASSO) for regression, or the Basis Pursuit for signal reconstruction, rely on $ \ell_1 $ minimization to find sparse solutions.
Moreover, the $ \ell_1 $ norm has a geometric interpretation as the sum of the lengths of the line segments from the origin to the point in each coordinate direction, which makes it the shortest path in a grid-like path structure, resembling taxicab geometry. This is why it is sometimes referred to as the Manhattan norm or taxicab norm.
Last updated