行稀疏 列稀疏 稀疏
In this article, I will try to demystify the idea of sparsity, one of the most important concepts empowering the prevailing multimedia industry. We shall learn different methods to analyze systems with sparse representations and discuss some specific applications, in domains like machine learning and computer vision, where these methods had a profound impact.
在本文中，我将试图揭开稀疏性的神秘面纱，稀疏性是使当前的多媒体行业发展壮大的最重要概念之一。 我们将学习不同的方法来分析具有稀疏表示的系统，并讨论机器学习和计算机视觉等领域中对这些方法产生深远影响的特定应用。
First, we shall begin by understanding how the data is represented in matrix form, then we will dive into a few important definitions and concepts — such as singular value decomposition — that would help us to appreciate the intricacies of different algorithms behind these applications.
首先，我们将从理解数据如何以矩阵形式表示开始，然后我们将深入探讨一些重要的定义和概念(例如奇异值分解)，这将有助于我们理解这些应用程序背后不同算法的复杂性。
Keywords: Singular Value Decomposition (SVD), Compressed Sensing, Regression, Recommendation Systems, Econometrics.
关键字：奇异值分解(SVD)，压缩感知，回归，推荐系统，计量经济学。
A vector or a matrix is said to be sparse if it has only a few non-zero entries.
如果向量或矩阵只有几个非零的条目，则称其为稀疏的 。
But, why do we want systems with sparse representations anyway?
但是，为什么我们仍然想要具有稀疏表示的系统？
We are drowning in information and starving for knowledge. — Rutherford D. Roger
我们淹没在信息中，渴望知识。 —卢瑟福·罗杰
Precisely, with the advent of Big Data, we need a reliable way of storing and representing the data. This brings us to the idea of sparsity, whose main goal is to reduce the dimensionality of the data for a more compact representation.
精确地，随着大数据的到来，我们需要一种可靠的存储和表示数据的方式。 这使我们想到了稀疏性的概念，其主要目的是减少数据的维数以实现更紧凑的表示。
Some general applications of sparse analysis include econometrics, genome-wide association, image denoising, image inpainting, image super-resolution, video surveillance, face recognition, and compressive sensing. We will look at a few of these applications towards the end of the article.
稀疏分析的一些一般应用包括计量经济学，全基因组关联，图像去噪，图像修复，图像超分辨率，视频监控，面部识别和压缩感测。 在本文结尾处，我们将介绍其中的一些应用程序。
This article tries to combine all these applications and will present a comprehensive explanation of sparsity and methods to analyze such systems. I must warn, it can be a little heavy in math, so I recommend readers to have some basic knowledge of linear algebra and optimization before reading any further. Nevertheless, I will try to define new terms and illustrate important concepts as and when required throughout this article. Sit tight and let’s begin…
本文试图结合所有这些应用程序，并将提供稀疏性和分析此类系统的方法的全面说明。 我必须警告，这可能会使您的数学工作有些繁重，因此我建议读者在进一步阅读之前先掌握线性代数和优化的一些基本知识。 尽管如此，在本文中需要的时候，我将尝试定义新的术语并说明重要的概念。 坐紧，开始吧...
The data is represented in matrix form as shown below.
数据以矩阵形式表示，如下所示。
This matrix A is called data or system matrix having m rows and n columns. It is also called a dictionary in compression applications, comprising the coefficients of discrete cosine transform (DCT) or discrete wavelet transform (DWT) of the input, while in image super-resolution A is a transformation matrix that converts a low-resolution image into a high-resolution image.
该矩阵A被称为具有m行和n列的数据或系统矩阵。 在压缩应用中也称为字典，包括输入的离散余弦变换(DCT)或离散小波变换(DWT)的系数，而在图像中，超分辨率A是将低分辨率图像转换为图像的变换矩阵。高分辨率图像。
In machine learning, each column vector in the data matrix A represents a feature. For example, consider you want to buy some groceries in the market. Each item is characterized by features such as weight (in kgs or pounds), percentage of discount, the price per unit, and so on.
在机器学习中，数据矩阵A中的每个列向量都代表一个特征。 例如，考虑您要在市场上购买一些杂货。 每件商品都具有诸如重量(以公斤或磅为单位)，折扣百分比，每单位价格等特征。
As stated earlier, the data matrix, here A, is considered sparse if it is represented efficiently using only a few of its entries.
如前所述，如果仅使用其中几个条目有效地表示数据矩阵，则认为这里的A稀疏。
Now let us recall few important definitions in linear algebra
现在让我们回想一下线性代数中的几个重要定义
The set of all linear combinations of vectors v1, v2, …,vn is called the span of these vectors and is written as Span{v1,…,vn}.
向量v1，v2，…，vn的所有线性组合的集合称为这些向量的跨度，并写为Span {v1，…，vn}。
For example, if vectors v1, v2, and v3 are linearly independent then
例如，如果向量v1，v2和v3 线性独立，则
Span{v1} is a line in R Span {v1}是R中的一行 Span{v1,v2} gives R² 跨度{v1，v2}给出R² Span{v1,v2,v3} gives R³ 跨度{v1，v2，v3}给出R³Let V be a vector space, then a set B of vectors is the basis for V if the vectors in B are linearly independent and Span B = V.
假设V为向量空间，则如果B中的向量线性独立且跨度B = V，则向量的集合B是V的基础。
For example, {[1, 0, 0], [0, 1, 0], [0, 0, 1]} are the basis for vector space R³.
例如，{[1，0，0]，[0，1，0]，[0，0，1]}是向量空间R 3的基础。
The rank of a matrix is defined as the maximum number of linearly independent row or column vectors in the matrix.
矩阵的秩定义为矩阵中线性独立的行或列向量的最大数量。
For example, the rank of the matrix
例如，矩阵的等级
is equal to 2.
等于2
Note: For any given matrix, the row rank equals the column rank.
注意：对于任何给定的矩阵，行等级等于列等级。
A square matrix U is said to be orthogonal if U’U = I. The rows and columns of orthogonal matrices are called orthonormal basis i.e., each has length one and are mutually perpendicular.
如果U'U = I，则称正方形矩阵U是正交的。正交矩阵的行和列称为正交基，即，每个矩阵的长度为1且相互垂直。
The general form of the matrix equation is Ax = b.
矩阵方程的一般形式是Ax = b。
Here A is the system or data matrix, x is a vector comprising the solutions of the equation, and b is the output. If we unravel each of these terms, we get
在此， A是系统或数据矩阵， x是包含方程式解的向量， b是输出。 如果我们解开这些术语中的每一个，我们都会得到
It is important to note that the output b can also be represented as a linear combination of columns vectors of A with elements in vector x as
重要的是要注意输出b也可以表示为A列向量与向量x中元素的线性组合
This is just a more intuitive form of matrix-vector multiplication.
这只是矩阵向量乘法的一种更直观的形式。
If the equation Ax=b does not have a solution, which is often the case in the real world, we can instead find the best approximate solution by minimizing the squares of the difference b-Ax, called the least squares as shown below.
如果方程Ax = b没有解(在现实世界中经常出现这种情况)，我们可以通过最小化差异b-Ax的平方(称为最小二乘)来找到最佳近似解，如下所示。
More specifically, our goal is to minimize the sum of squares of errors between Ax and output b.
更具体地说，我们的目标是使Ax与输出b之间的误差平方和最小。
However, if A is an under-determined i.e., it contains more unknowns than equations, there is no closed-form solution. For any under-determined system, the number of columns is greater than the number of rows. Therefore, there are more number of features than observations or samples, m<n. Moreover, these systems usually have infinitely many solutions, making the model too explicit. The solutions can easily overfit the data, affecting the model to become incapable of generalization.
但是，如果A是一个欠定的，即它包含的未知数多于方程式，则没有封闭形式的解。 对于任何不确定的系统，列数大于行数。 因此，特征数量多于观测值或样本， m < n 。 而且，这些系统通常具有无限多个解决方案，这使得模型过于明确。 这些解决方案可以轻松地使数据过度拟合 ，从而影响模型的泛化能力。
To solve such problems we need to restrict the solution space by incorporating some prior knowledge about the data, using regularization.
为了解决此类问题，我们需要通过使用正则化合并一些有关数据的先验知识来限制解决方案空间。
Before talking about regularization, let us look at SVD, one of the most important concepts in linear algebra which assert that any matrix, for instance, X, can be decomposed (or factorized) into a product of three matrices.
在讨论正则化之前，让我们看一下SVD，它是线性代数中最重要的概念之一，它断言任何矩阵(例如X )都可以分解(或分解)为三个矩阵的乘积。
where both U and V are orthogonal matrices and Σ is a diagonal matrix.
其中U和V都是正交矩阵，而Σ是对角矩阵。
We refer to the values σ1,σ2,…, σn as singular values, vectors u1,u2,…, un are left singular vectors, and vectors v1,v2,…, vn are right singular vectors.
我们将值σ1，σ2，…，σn称为奇异值，向量u1，u2，…，un是左奇异矢量，向量v1，v2，…，vn是右奇异矢量。
The singular values are always non-negative and are in descending order i.e., σ1 ≥ σ2 ≥ ….. ≥ σn, corresponding to the relative importance of each term in the expansion
奇异值始终为非负值，并且按降序排列，即σ1≥σ2≥…..≥σn，对应于扩展中每个项的相对重要性
Each term, in the above sum, has rank 1. After all, it depends only on one column vector and one row vector (remember for any matrix row rank is equal to column rank). Thus, the matrix X approximates to first k-terms giving the closest k-dimensional representation of matrix X.
在上述总和中，每个项的等级均为1。毕竟，它仅取决于一个列向量和一个行向量(记住任何矩阵行等级等于列等级)。 因此，矩阵X近似于给出矩阵X的最接近k维表示的前k个项。
For example, the best rank-one approximation of the matrix X is given by u1σ1v1'.
例如，矩阵X的最佳秩一近似由u1σ1v1'给出。
This notion of decomposing the matrix as a sum of rank 1 matrices can be used to solve the rank minimization problem stated as
这种将矩阵分解为1级矩阵之和的概念可用于解决如下所述的秩最小化问题
where ||.||F is called Frobenius norm.
||。|| F称为Frobenius范数。
Essentially, we are trying to find the best rank r approximation of matrix A by minimizing the Frobenius norm between approximate A^ and A.
本质上，我们试图通过最小化近似A ^和A之间的Frobenius范数来找到矩阵A的最佳秩r近似。
A Frobenius norm of a matrix is the square root of the sum of the entries
矩阵的Frobenius范数是条目总和的平方根
The solution to this problem is sparse and can found using singular value decomposition, in the sense that all except first r-singular values are trivial.
从第一个r奇异值之外的所有值都是微不足道的意义上讲，此问题的解决方案很少，可以使用奇异值分解找到。
There are several variants of singular value decomposition such as principle component analysis (PCA), Robust PCA, linear discriminant analysis (LDA), etc.
奇异值分解有多种变体，例如主成分分析(PCA)，鲁棒PCA，线性判别分析(LDA)等。
It turns out that the right singular vectors are nothing but the eigenvectors of the matrix X’X and the left singular vectors are the eigenvectors of matrix XX’. The eigenvalues of the symmetric positive semidefinite matrix X’X are given by the squares of corresponding singular values σ1,σ2,…,σn of X.
事实证明，右奇异向量仅是矩阵X'X的特征向量，而左奇异向量是矩阵XX'的特征向量。 对称正半定矩阵X'X的特征值由X的对应奇异值σ1，σ2，…，σn的平方给出。
As discussed earlier, using regularization we can constrain the solution space by incorporating some prior knowledge into the problem, such as the solution x is sparse (or small).
如前所述，使用正则化可以通过将一些先验知识纳入问题来约束解空间，例如解x稀疏(或较小)。
Considering the solutions of the equations Ax=b sparse will make the system more robust and in turn prevent the model from overfitting.
考虑方程Ax = b稀疏的解，将使系统更健壮，进而防止模型过度拟合。
The norm of the matrix achieves the regularization. A norm is a function from a vector space that satisfies certain properties related to scalability and additivity and takes the value zero only if the input vector is zero.
矩阵的范数实现正则化。 范数是向量空间中的函数，其满足与可伸缩性和可加性相关的某些属性，并且仅当输入向量为零时才将值设为零。
When the model regularized using l2 norm the problem of finding the optimal solutions is called Ridge, the model regularized using l1 norm the problem of finding the optimal solutions is called Lasso.
当使用l2范数正则化的模型找到最优解的问题称为Ridge时，将使用l1范数正则化的模型找到最优解的问题称为Lasso。
Among the norms related to the regularization of the model, only l1 norm and lp norm (0<p<1) are proven to give sparse solutions. Nevertheless, we shall discuss each one of these norms in the coming few sections.
在与模型正则化相关的范数中，只有l1范数和lp范数(0 <p <1)被证明可提供稀疏解。 尽管如此，我们将在接下来的几节中讨论这些规范中的每一个。
The l2 norm or euclidean norm of a vector x is
向量x的l2范数或欧几里德范数是
As discussed earlier, we are trying to find the optimal solutions for the least-squares problem
如前所述，我们正在尝试找到最小二乘问题的最佳解决方案
By regularizing the equation Ax=b using l2 norm, we get
通过使用l2范数对方程Ax = b进行正则化，我们得到
We can visualize the solution space of this problem in 2D as shown below.
我们可以在2D中可视化此问题的解决方案空间，如下所示。
Apparently, while l2 norm can regularize the model it cannot yield sparse solutions.
显然，虽然l2范数可以规范化模型，但它不能产生稀疏解。
By swapping the constraint and objective we can rewrite the same problem as shown below.
通过交换约束和目标，我们可以重写相同的问题，如下所示。
This reformulates into the Lagrangian form as
重新格式化为拉格朗日形式
Notice that here we added an extra term λ ||x||2 that affects the regularization of the model.
请注意，这里我们添加了一个额外的项λ|| x || 2，它影响模型的正则化。
This way of regularizing the model using a l2 norm is called a Ridge problem. The parameter, in fact, hyperparameter λ controls the amount of regularization. There is a one-to-one correspondence between λ and S, where both constrain the values of x and optimal values of these parameters are usually data-dependent.
使用l2范数对模型进行正则化的这种方式称为Ridge问题。 实际上，参数超参数λ控制正则化的量。 λ和S之间存在一一对应的关系，其中两者都约束x的值，而这些参数的最佳值通常取决于数据。
The l0 norm of a vector x is the number of all non-zero entries of x
一个向量x的范数L 0是x的所有非零项的数量
By using l0 norm to regularize, the problem becomes
通过使用l0范数进行正则化，问题就变成了
We can visualize the solution space in 2D as shown below.
我们可以将二维解决方案空间可视化，如下所示。
We can see that, though we obtain sparse solutions using l0 norm, they are not unique. Moreover, since the l0 norm is non-convex, solving this problem is NP-hard. However, there are some greedy algorithms such as Matching Pursuit, to solve such problems.
我们可以看到，尽管我们使用l0范数获得了稀疏解，但是它们并不是唯一的。 而且，由于l0范数是非凸的，因此解决此问题很困难。 但是，有一些贪婪算法(例如Matching Pursuit)可以解决此类问题。
The l1 norm of a vector x is
向量x的l1范数是
By adding the l1 norm to the above problem, we can obtain sparse solutions i.e., zeroing the effect of lesser important features. For example, if
通过将l1范数添加到上述问题中，我们可以获得稀疏解，即将次要特征的影响归零。 例如，如果
The solutions are simply
解决方案很简单
Therefore, the problem to solve becomes
因此，要解决的问题成为
We can visualize the solution space in 2D as shown below.
我们可以将二维解决方案空间可视化，如下所示。
Again, by swapping the constraint and objective we can rewrite the same problem as shown below.
同样，通过交换约束和目标，我们可以重写相同的问题，如下所示。
This is called Lasso Problem, with constraint S limiting the values of x, thereby forcing the optimization algorithm to yield sparse solutions.
这被称为套索问题，其中约束S限制x的值，从而迫使优化算法产生稀疏解。
The same problem is reformulated into the Lagrangian form as
将相同的问题重新表述为拉格朗日形式
Though the Lasso yields sparse solutions, unlike Ridge, there are no closed-form solutions. However, we can use several methods including matching pursuit, orthogonal matching pursuit, fast iterative shrinkage algorithm (FISTA), and alternative direction method of multipliers to solve the optimization problem.
尽管套索产生的稀疏解与Ridge有所不同，但没有封闭形式的解。 但是，我们可以使用多种方法来解决优化问题，这些方法包括匹配追踪，正交匹配追踪，快速迭代收缩算法(FISTA)和乘数的替代方向方法。
Sometimes the Lasso problem is also called a Basis Pursuit problem. Essentially both are the same and used interchangeably. However, the term Lasso is more popular in the mathematics community.
有时，套索问题也称为基本追求问题。 本质上两者是相同的，并且可以互换使用。 但是，“套索”一词在数学界更为流行。
The generalized lp norm for a vector x is
向量x的广义lp范数是
where 0<p<1.
其中0 <p <1。
By adding lp norm to the given problem
通过将lp规范添加到给定的问题
We can visualize the solution space in 2D as shown below.
我们可以将二维解决方案空间可视化，如下所示。
By swapping the constraint and objective we can rewrite the problem as shown below.
通过交换约束和目标，我们可以重写问题，如下所示。
The same problem reformulates into the Lagrangian form as below.
相同的问题重新形成拉格朗日形式，如下所示。
Using lp norm though we can obtain sparse solutions, the lp norm is non-convex and hence the problem becomes NP-hard.
使用lp范数，虽然我们可以获得稀疏解，但lp范数是非凸的，因此问题变得很棘手。
The figure shown below summarizes all the norms for regularization
下图显示了所有正则化规范
Out of all these norms, the l1 norm is the best choice for regularization.
在所有这些规范中，l1规范是进行正则化的最佳选择。
Now, we shall examine a few applications where sparsity is employed. In all these applications, the formulation of the problem remains mostly the same only the approach for finding the solutions changes.
现在，我们将研究一些使用稀疏性的应用程序。 在所有这些应用程序中，问题的表述大部分只与查找解决方案的方法相同。
Econometrics deals with predicting quantities related to the economy of a business or any entity per se. It involves testing and evaluating various economic theories and hypothesis that help government and businesses to formulate appropriate policies.
计量经济学处理与企业或任何实体本身的经济相关的预测数量。 它涉及测试和评估各种经济理论和假设，以帮助政府和企业制定适当的政策。
Regression is widely used for solving various problems in econometrics. It is a technique for finding the correlation between a dependent variable (y) and a series of independent variables (xi). In linear regression, the dependent variable has a direct relationship with the independent variables as shown below.
回归被广泛用于解决计量经济学中的各种问题。 它是一种用于找到因变量(y)和一系列自变量(xi)之间的相关性的技术。 在线性回归中，因变量与自变量具有直接关系，如下所示。
For example, if a person working in a company received a wage y, then x1 can be the amount of training, x2 can be his years of experience, and so on.
例如，如果在公司工作的人收到工资y，则x1可以是培训的金额，x2可以是他的工作年限，依此类推。
Note that in the above equation, the weights of each independent variable xi is denoted by α1, α2,…..αn and x1, x2,…, xn do not correspond to the values of vector x in Ax=b. They are actually the values of each row in matrix A and α1, α2,…αn are in fact the values of x in Ax=b.
注意，在上式中，每个自变量xi的权重由α1，α2，.....αn表示，而x1，x2，...，xn与Ax = b中的向量x的值不对应。 它们实际上是矩阵A中每一行的值，而α1，α2，...αn实际上是Ax = b中x的值。
We know that the general form of matrix equation is Ax=b.
我们知道矩阵方程的一般形式是Ax = b。
This can also be formulated as a regression problem, where the output b is simply a linear combination of elements in matrix A i.e., matrix-vector multiplication of elements of A and vector x as shown below.
这也可以表述为回归问题，其中输出b只是矩阵A中元素的线性组合，即A元素和矢量x的矩阵向量乘积，如下所示。
Each element x, also called weight, indicate the extent of contribution of each feature to the final output. Thus, finding the optimal values of x, denoted by x*, is usually the objective of such problems.
每个元素x(也称为权重)指示每个特征对最终输出的贡献程度。 因此，找到x的最佳值，由X *表示时，通常是物镜的这种问题。
Note: In linear algebra, the same problem is stated as finding the coefficients x* that gives a vector in Span<a_1,a_2,….a_n> closest to b.
注意：在线性代数中，存在同样的问题，即找到系数x *，该系数在Span <a_1，a_2，.... a_n>中给出最接近b的向量。
The closed-form solution is
封闭形式的解决方案是
X+ = (X^TX)-1X^T is the pseudoinverse or generalized inverse (more specifically Moore-Penrose inverse) of X.
X + =(X ^ TX)-1X ^ T是X的伪逆或广义逆(更具体Moore-Penrose逆)。
Note: The pseudoinverse itself is computed using Singular Value Decomposition (SVD).
注意：伪逆本身是使用奇异值分解(SVD)计算的。
The general assumption across all the regression algorithms is that these feature vectors ai are independent of each other i.e. ai forms an orthonormal basis.
所有回归算法的一般假设是这些特征向量ai彼此独立，即ai形成正交标准。
We solved the regression problem by finding the optimal values, x*. However, if the system is under-determined i.e. when the given dataset is essentially small, we can leverage different regularization techniques discussed earlier to prevent the model from overfitting.
我们通过找到最佳值x *解决了回归问题。 但是，如果系统不确定，即当给定数据集基本很小时，我们可以利用前面讨论的不同正则化技术来防止模型过度拟合。
Netflix launched this challenge in 2006 to improve the recommendations of movies to its customers. SVD played a central role in most of the top-performing algorithms.
Netflix于2006年发起了这一挑战，以改善对客户的电影推荐。 SVD在大多数性能最高的算法中起着核心作用。
The provided data in this challenge is largely scarce with several empty entries.
这项挑战中提供的数据在很大程度上缺少几个空条目。
Each entry corresponds to the rating of a customer to a particular movie and each column has several ratings consigned by different customers.
每个条目对应于客户对特定电影的评级，并且每一列具有由不同客户委托的多个评级。
The main goal was to recover the complete matrix, from the given limited observations, by finding the best approximation of ratings in the empty entries. These ratings can be used for recommending movies to other customers bearing similar patterns.
主要目标是通过在空条目中找到评级的最佳近似值，从给定的有限观察中恢复完整的矩阵。 这些等级可用于向其他具有类似模式的客户推荐电影。
Therefore, we are essentially trying to seek an approximate of A^ that imputes all the missing entries in A, a problem called as matrix completion.
因此，我们基本上是试图寻求一种近似的^这一切归咎于A中缺少的条目，一个被称为矩阵完成问题。
One way to solve this is by constraining the rank of A. So the optimization problem to be solved is
解决此问题的一种方法是限制A的等级。 所以要解决的优化问题是
or simply
或简单地
This problem is non-convex and requires some heuristic knowledge to find local minima. We start with an initial guess for missing values and then iterate by minimizing the rank until convergence.
这个问题是非凸的，需要一些启发式知识才能找到局部极小值。 我们从对丢失值的初始猜测开始，然后通过最小化等级直至收敛进行迭代。
An alternative approach is to use the nuclear norm for which exact solutions are derivable. The nuclear norm of a matrix is simply the sum of its singular values. It is also called the trace norm.
一种替代方法是使用可导出精确解的核规范。 矩阵的核范数只是其奇异值的总和。 它也称为跟踪规范。
We can define a project operator, over subset Ω of observed entries, that replaces the missing entries with zeros and leaves the observed entries alone
我们可以定义一个项目算子，在观测条目的子集Ω上，将缺失的条目替换为零，而将观测条目保留下来
Therefore, the optimization problem to be solved becomes
因此，要解决的优化问题变成
where ||.||* is the nuclear norm
||。|| *是核规范
We again start with an initial guess of missing entries, find the full rank of the resultant matrix, and then threshold its singular values (using SVD) to obtain new estimates of missing entries. This process is repeated until the problem converges.
我们再次从丢失条目的初始猜测开始，找到结果矩阵的完整等级，然后阈值其奇异值(使用SVD)以获得丢失条目的新估计。 重复此过程，直到问题收敛为止。
Note: In practice, we allow the A^ to make some errors on the given data to prevent the model from overfitting.
注意：实际上，我们允许A ^在给定数据上犯一些错误，以防止模型过度拟合。
You can find similar applications of recommendation systems in amazon.com, Target, Walmart, etc.
您可以在amazon.com，Target，Walmart等中找到推荐系统的类似应用程序。
In video surveillance, each input frame B of the video separated into background L (stationary part) and foreground E (moving parts).
在视频监视中，视频的每个输入帧B分为背景L (固定部分)和前景E (移动部分)。
Since the background is essentially the same in every input frame, it can be characterized by a low-rank matrix (a rank minimization problem).
由于背景在每个输入帧中基本相同，因此可以通过低秩矩阵来表征(秩最小化问题)。
On the other hand, the moving parts take only a limited part of the input frame and thus represented using a sparse matrix (a regularization problem).
另一方面，运动部分仅占据输入帧的有限部分，因此使用稀疏矩阵表示(正则化问题)。
Therefore, the resultant problem formulated as shown below.
因此，产生的问题如下所示。
This can be solved using singular value decomposition, where the background L is decomposed into the product UΣ V’. Since the rank of the L is constrained to k, we are only interested in first k singular values. Therefore we can rewrite the problem as
这可以通过奇异值分解来解决，其中背景L分解为乘积UΣV'。 由于L的秩被限制为k ，我们只对前k个奇异值感兴趣。 因此我们可以将问题改写为
However, this is an NP-hard problem so we need to introduce the nuclear norm. The resultant problem is
但是，这是一个NP问题，因此我们需要引入核规范。 结果是
where ||.||* is the nuclear norm
||。|| *是核规范
If the singular value decomposition of A is A=UΣ V’. Let σ denote the vector containing all singular values of A. Then
如果A的奇异值分解为A =UΣV'。 令σ表示包含A的所有奇异值的向量。 然后
||σ||0 equals the rank of A
||σ|| 0等于A的等级
||σ||1 equals the nuclear norm of A
||σ|| 1等于A的核范数
||σ||2 equals the Frobenius norm of A
||σ|| 2等于A的Frobenius范数
Compressed sensing (also known as compressive sensing, compressive sampling, or sparse sampling) is a technique for efficiently acquiring and reconstructing a signal, by finding solutions to under-determined linear systems.
压缩感测(也称为压缩感测，压缩采样或稀疏采样)是一种通过找到欠定线性系统的解来有效获取和重建信号的技术。
The flowchart of a typical image acquisition process is as shown below.
典型的图像获取过程的流程图如下所示。
Compressed sensing is based on the assumption that the image can be represented sparsely by sampling at a frequency less than the Nyquist frequency. The image is expected to have some redundancies, in fact, it is impossible to compress any image that has no redundancies — such as pure noise. These redundancies are essentially due to correlations present in the data.
压缩感测基于以下假设：可以通过以小于奈奎斯特频率的频率采样来稀疏表示图像。 期望图像具有某些冗余，实际上，不可能压缩任何没有冗余的图像，例如纯噪声。 这些冗余基本上是由于数据中存在相关性。
So, the goal of any compression algorithm is to decorrelate these correlations present in the data, identify the importance of each and in turn, if feasible, reduce some to zero.
因此，任何压缩算法的目标都是去关联数据中存在的这些相关性，确定每个相关性的重要性，然后在可行的情况下将某些相关性降低为零。
The image is compressed by sampling at a frequency (M) lower than the Nyquist frequency (N). This sparse representation of the image can be easily transmitted or stored and when required it is reconstructed to emulate the quality of the original image. However, we can expect some perceptual redundancies, if not some loss, since this is a compression after all. The recovered signal obtained from Ax*.
通过以低于奈奎斯特频率( N )的频率( M )采样来压缩图像。 图像的这种稀疏表示可以轻松地传输或存储，并且在需要时可以对其进行重构以模拟原始图像的质量。 但是，我们可以期待一些感知上的冗余，即使不是一些损失，因为这毕竟是一种压缩。 从Ax *获得的恢复信号。
Consider the following example
考虑以下示例
The image on the left is the original image in grayscale. The image on the right is the compressed image formed by reducing some intensity values to zero. 左边的图像是灰度的原始图像。 右边的图像是通过将一些强度值减小到零而形成的压缩图像。You can see the effect of reducing the intensity values of some pixels to zero. Though the resultant compressed image is sparse, this method is naive since we are inadvertently losing too many details.
您会看到将某些像素的强度值减小为零的效果。 尽管生成的压缩图像很稀疏，但是这种方法很幼稚，因为我们无意间丢失了太多细节。
Below is a much better compression!
下面是一个更好的压缩方式！
Compressed image 压缩影像The concept of sparsity is employed in almost every domain and therefore it’s important to know the underlying intricacies to appreciate these applications. There are many other applications of sparsity in domains like neuroscience, medical imaging, etc but maybe for another article.
稀疏性的概念几乎在每个领域中都被使用，因此了解潜在的复杂性以欣赏这些应用程序非常重要。 稀疏性在神经科学，医学影像学等领域还有许多其他应用，但也许在另一篇文章中。
I hope you enjoyed reading it. Let me know your comments below 👇.
希望您喜欢阅读。 让我知道您在below下面的评论。
Originally published at https://saidarahas.com on August 26, 2020.
最初于 2020年8月26日 在 https://saidarahas.com 上 发布 。
翻译自: https://medium.com/@saidarahas/an-ultimate-guide-to-sparse-analysis-a-mathematical-perspective-48fa7045d1a0
行稀疏 列稀疏 稀疏
