從稀疏表示到低秩表示（一）

確定研究方向后一直在狂補(bǔ)理論，最近看了一些文章，有了些想法，順便也總結(jié)了representation系列的文章，由于我剛接觸，可能會(huì)有些不足，愿大家共同指正。

從稀疏表示到低秩表示系列文章包括如下內(nèi)容：

一、sparse representation

二、NCSR（NonlocallyCentralized Sparse Representation）

三、GHP（GradientHistogram Preservation）

四、Group sparsity

五、Rankdecomposition

一、 sparse representation

1 sparsity

一個(gè)線性表示解決的問題如下圖所示：

但是，數(shù)據(jù)量增大后，這個(gè)線性表達(dá)的基求解十分復(fù)雜，而且很多是冗余的，稀疏表示能解決這個(gè)問題：

稀疏直觀理解就是在滿足誤差小和非零項(xiàng)盡可能多，非零項(xiàng)就是解決l₀-norm問題，但是這個(gè)約束太強(qiáng)，弱化條件就是l₁-norm，這是個(gè)Convex Optimization，于是有一系列的l_p-norm。

關(guān)于l_p-norm的求解方法如上圖所示，所有的paper用到的方法都在之內(nèi)。稀疏表達(dá)的應(yīng)用就非常廣泛了，包括去噪，去霧，分割，分類，人臉識(shí)別等。

2 why sparse?

關(guān)于稀疏的可行原理要追溯到神經(jīng)科學(xué)的突破上，emergence of simple-cell receptive field propertiesby learning a sparse code for nature images.于1996年Cornell大學(xué)心理學(xué)院的Bruno在Nature上發(fā)表的文章。

結(jié)論：哺乳動(dòng)物的初級(jí)視覺的簡(jiǎn)單細(xì)胞的感受野具有空域局部性、方向性和帶通性（在不同尺度下，對(duì)不同結(jié)構(gòu)具有選擇性）,和小波變換的基函數(shù)具有一定的相似性。

而后的概率貝葉斯probabilistic Bayes perspective目標(biāo)函數(shù)相似：

接著是上世紀(jì)末的comprehensive sensing解決信號(hào)的稀疏等，現(xiàn)在大量用于機(jī)器視覺圖像理解和分類上。

無論是去噪還是圖像恢復(fù)都是解決如下的問題：

Imagereconstruction: the problem：

詳細(xì)的優(yōu)化過程如下:

Image reconstruction by sparse coding---the basic procedures

3 How sparsityhelps?

An interesting example:

Suppose you are looking for agirlfriend/boyfriend.

– i.e., you are“reconstructing” the desired signal.

• Your objective is that she/he is “白-富-美”/ “高-富-帥”.

– i.e.,you want a “clean” and “perfect”reconstruction.

• However, the candidates are limited.

– i.e.,the dictionary is small.

• Can you findyour ideal girlfriend/boyfriend?

假設(shè)你設(shè)定某些單一的標(biāo)準(zhǔn)，如handsome、 rich， tall，那么這些相當(dāng)于basis,針對(duì)具體的樣本人選，根據(jù)其特征映射這些basis，然后權(quán)衡，choose the best candidate.

•Candidate Ais tall; however, he is not handsome.

•Candidate Bis rich; however, he is too fat.

•Candidate Cis handsome; however, he is poor.

• If yousparselyselect one of them, none is ideal foryou

– i.e., asparse representation vectorsuch as [0, 1, 0].

• How about adensesolution: (A+B+C)/3?

– i.e.,a dense representation vector [1,1, 1]/3

– The “reconstructed” boyfriend is acompromiseof “高-富-帥”, and he is fat (i.e., has some noise) at the same time.

Sowhat’s wrong?

– This is becausethedictionaryis toosmall!

• If you can select yourboyfriend/girlfriend from boys/girls all over the world (i.e.,a largeenough dictionary), there is a very high probability (nearly 1) that you will find him/her!– i.e.,a very sparse solution such as [0, …, 1, …, 0]

• In summary, asparsesolution with anover-completedictionaryoften works!

•Sparsityandredundancyare the two sides of the same coin.

4 what is the dictionary?

縱觀所有的重構(gòu)問題，或多或少多設(shè)計(jì)dictionarylearning 問題，具體的方法的總結(jié)和應(yīng)用可以參考（圖像分類的字典學(xué)習(xí)方法概述），全面的介紹各種dictionary learning 貌離神合的相似。

5 Does sparse enough?

It just sparsethe representation and reduce the redundancy, so how about the similarity andstructure between the atoms? What if there is corruption such as light etc.noise, it can’t be robust to various noises.

Such asNonlocalself-similarity

6 Beyond sparse

Limitations of sparse representation

1)sparse representation often learns a dictionary on the basis ofwell-construct and compact dictionary, once the input data has changed, it willcost additional time to construct a new dictionary;

2)If the training data is contaminated (i.e.occlusion,disguise, lighting variations, pixel corruptionetc.) , sparse is notrobust and will be deteriorate;

3)When the data to be analyzed from the same class and sharingcommon (correlated) features(i.e. texture),sparse coding would be still performed for each input signalindependently, it lacksstructureand correlations within and between classes.

So how to find efficientrepresentation ?

1)Structure:

Data enough: relations within class, regularized nearest space

Data small: across class representations, collaborativerepresentation

2) Robust: low-rank decomposition & sparsenoise

最后，推薦一篇低秩原理和應(yīng)用的綜述：http://media.au.tsinghua.edu.cn/2013_ATCA_Review.pdf

未完，待續(xù)，更多請(qǐng)關(guān)注：http://blog.csdn.net/tiandijun，歡迎交流！

總結(jié)

以上是生活随笔為你收集整理的从稀疏表示到低秩表示（一）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。