constr_structure_group.hpp

Go to the documentation of this file.

#ifndef MLPACK_CORE_OPTIMIZERS_FW_CONSTR_STRUCTURE_GROUP_HPP
#define MLPACK_CORE_OPTIMIZERS_FW_CONSTR_STRUCTURE_GROUP_HPP

#include <mlpack/prereqs.hpp>
#include "constr_lpball.hpp"

namespace mlpack {
namespace optimization {

template<typename GroupType>
class ConstrStructGroupSolver
{
 public:
  ConstrStructGroupSolver(GroupType& groupExtractor) :
    groupExtractor(groupExtractor)
  { /* Nothing to do */ }

  void Optimize(const arma::mat& v, arma::mat& s)
  {
    size_t nGroups = groupExtractor.NumGroups();
    double dualNorm = 0;
    size_t optimalGroup = 1;

    // Find the optimal group.
    for (size_t i = 1; i <= nGroups; ++i)
    {
      arma::vec y;
      groupExtractor.ProjectToGroup(v, i, y);
      double newNorm = groupExtractor.DualNorm(y, i);

      // Find the group with largest dual norm.
      if (newNorm > dualNorm)
      {
        optimalGroup = i;
        dualNorm = newNorm;
      }
    }

    groupExtractor.OptimalFromGroup(v, optimalGroup, s);
  }

 private:
  GroupType& groupExtractor;
};

class GroupLpBall
{
 public:
  GroupLpBall(const double p,
              const size_t dimOrig,
              std::vector<arma::uvec> groupIndicesList):
    p(p), numGroups(groupIndicesList.size()),
    dimOrig(dimOrig),
    groupIndicesList(groupIndicesList),
    lpBallSolver(p)
  {/* Nothing to do. */}

  void ProjectToGroup(const arma::mat& v, const size_t groupId, arma::vec& y)
  {
    arma::uvec& indList = groupIndicesList[groupId - 1];
    size_t dim = indList.n_elem;
    y.set_size(dim);

    for (size_t i = 0; i < dim; ++i)
      y(i) = v(indList(i));
  }

  void OptimalFromGroup(const arma::mat& v, const size_t groupId, arma::mat& s)
  {
    // Project v to group.
    arma::vec yk;
    ProjectToGroup(v, groupId, yk);

    // Optimize in this group.
    arma::vec sProj(yk.n_elem);
    lpBallSolver.Optimize(yk, sProj);

    // Recover s to the original dimension.
    arma::uvec& indList = groupIndicesList[groupId - 1];
    size_t dim = indList.n_elem;  // dimension of the group.
    s.zeros(dimOrig, 1);

    for (size_t i = 0; i < dim; ++i)
      s(indList(i)) = sProj(i);
  }

  size_t NumGroups() const {return numGroups;}
  size_t& NumGroups() {return numGroups;}

  double DualNorm(const arma::vec& yk, const int groupId)
  {
    if (p == std::numeric_limits<double>::infinity())
    {
      // inf-norm, return 1-norm
      return arma::norm(yk, 1);
    }
    else if (p > 1.0)
    {
      // p norm, return q-norm
      double q = 1.0 / (1.0 - 1.0/p);
      return  arma::norm(yk, q);
    }
    else if (p == 1.0)
    {
      // 1-norm, return inf-norm
      return arma::norm(yk, "inf");
    }
    else
    {
      Log::Fatal << "Wrong norm p!" << std::endl;
      return 0.0;
    }
  }

 private:
  double p;

  size_t numGroups;

  size_t dimOrig;

  std::vector<arma::uvec> groupIndicesList;

  ConstrLpBallSolver lpBallSolver;
};


} // namespace optimization
} // namespace mlpack



#endif