0
\$\begingroup\$

For my project in machine learning supervised, I have to simplify a training-data and I have to use this technique at page 5 of the document.

Pseudocode algorithm

My code (numbers are the steps):

import numpy as np
import math
def GAD(X): 
    # 1. Initialize
    l=0
    D=[]
    I=[]
    R = np.copy(X)

    # 2. repeat l=<N (look algorithm) 
    while l<X.shape[0]: 
        # 3. Find residual column (l1 to l2 norm ratio)
        min_eps = float('inf') # to search min initialize to infinite
        j_min   =   -1
        for j in range(R.shape[1]): 
            norma1 = norma2 = 0
            for i in range(R.shape[0]): 
                norma1 += abs(R[i][j])
                norma2 += (R[i][j])**2
            norma2 = math.sqrt(norma2)
            eps = norma1/norma2   # sparsity index
            if min_eps > eps and j not in I: #excludes if already inserted
                min_eps=eps
                j_min = j
        # 4. Set the l-th atom equal to normalized
        norma2 = np.sqrt(np.sum(R[:, j_min]**2, axis=0)) 
        atomo = R[:, j_min]/norma2   
        # 5. Add to the dictionary
        if len(D) == 0:
            D = np.asarray(atomo)
        else:
            D = np.vstack((D, atomo.T))
        I.append(j_min)
        # 6. Compute the new residual    
        for j in range(R.shape[1]): 
            R[:, j] = R[:, j]-atomo*(atomo.T*R[:, j]) 
        l = l+1
    # 7. Termination (read page 6 of the document)
    return D,I

I have some doubts:

  1. Is it a correct implementation (observe mostly steps 5 and 6 in the pseudocode algorithm)?
\$\endgroup\$

closed as off-topic by Gareth Rees, Sᴀᴍ Onᴇᴌᴀ, Mast, t3chb0t, Vogel612 Jan 30 '18 at 21:11

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions containing broken code or asking for advice about code not yet written are off-topic, as the code is not ready for review. After the question has been edited to contain working code, we will consider reopening it." – Gareth Rees, Sᴀᴍ Onᴇᴌᴀ, Mast, t3chb0t, Vogel612
If this question can be reworded to fit the rules in the help center, please edit the question.

2
\$\begingroup\$

I haven't read the paper so don't necessarily understand the algorithm, but this seems wrong to me:

    # 3. Find residual column (l1 to l2 norm ratio)
    min_eps = float('inf') # to search min initialize to infinite
    j_min   =   -1
    for j in range(X.shape[1]): 
        norma1 = norma2 = 0
        for i in range(X.shape[0]): 
            norma1 += abs(X[i][j])
            norma2 += (X[i][j])**2
        norma2 = math.sqrt(norma2)
        eps = norma1/norma2   # sparsity index
        if min_eps > eps and j not in I: #excludes if already inserted
            min_eps=eps
            j_min = j

The pseudocode says to find the column of \${\mathbf R}^l\$ with minimum ratio, but this code finds the column of \$\mathbf X\$ with minimum ratio.

Have you tested your code and made sure it returns the correct result?

\$\endgroup\$
  • \$\begingroup\$ You're really right, thanks! But I don't know if it's correct, because I do not know what the "D" and "I" values represent. Can you help me to understand this doubt? PS You don't understand all paper, only page 5 \$\endgroup\$ – Giuseppe Accardo Jan 30 '18 at 16:54
  • 1
    \$\begingroup\$ @giuseppeaccardo: If you don't know what \$\mathbf D\$ and \$\mathbf I\$ represent, then I think your question might not be suitable for Code Review. This isn't a site for getting explanations of algorithms. \$\endgroup\$ – Gareth Rees Jan 30 '18 at 17:15
  • \$\begingroup\$ I've understood what D and I represent. I think that the problems are in the step 5 and 6. Do you think they were implemented well by observing the algorithm? Maybe I was wrong with the algebraic form \$\endgroup\$ – Giuseppe Accardo Jan 31 '18 at 1:24
  • \$\begingroup\$ This was the correct of the step number 6 R[:, j] = R[:, j]-(atomo*( np.inner(atomo.T, R[:, j]))) \$\endgroup\$ – Giuseppe Accardo Feb 1 '18 at 10:40

Not the answer you're looking for? Browse other questions tagged or ask your own question.