2x1=10

because numbers are people, too
Persönliches
Fotografie
Programmierung
    • Quadratic interpolation given two points and one derivative

      While read­ing up on line search algo­rithms in non­lin­ear opti­miza­tion for neur­al net­work train­ing, I came across this prob­lem: Giv­en a func­tion \(f(x)\) , find a qua­drat­ic inter­polant \(q(x) = ax^2 + bx + c\) that ful­fills the con­di­tions \(f(x_0) = q(x_0)\) , \(f(x_1) = q(x_1)\) and \(f'(x_0) = q'(x_0)\) . Basi­cal­ly this:

      Quadratic interpolation of f(x) through two points

      So I took out my scrib­bling pad, wrote down some equa­tions and then, after two pages of non­sense, decid­ed it real­ly wasn’t worth the has­sle. It turns out that the sim­ple sys­tem


      \begin{align}
      f(x_0) &= ax_0^2 + bx_0 + c\\
      f(x_1) &= ax_1^2 + bx_1 + c\\
      f'(x_0) &= 2ax_0 + b
      \end{align}

      for


      \begin{align}
      q(x) &= ax^2 + bx + c
      \end{align}

      has the solu­tion


      \begin{align}
      a &= - \frac{f(x_0) - f(x_1) - x_0 f'(x_0) + x_1 f'(x_0)}{(x_0 - x_1)^2} \\
      b &= - \frac{x_0^2 f'(x_0) - x_1^2 f'(x_0) - 2x_0 f(x_0) + 2x_0 f(x_1)}{(x_0 - x_1)^2} \\
      c &= \frac{x_0^2 f(x_1) + x_1^2 f(x_0) - 2x_0 x_1 f(x_0) - x_0 x_1^2 f'(x_0) + x_0^2 x_1 f'(x_0)}{(x_0 - x_1)^2}
      \end{align}

      Instead of ruin­ing your time on the paper, it can be obtained more eas­i­ly in Mat­lab using

      syms a b c x_0 x_1 f(x_0) f(x_1) df(x_0)
      [a, b, c] = solve(...
            f(x_0) == a*x_0^2 + b*x_0 + c, ...
            f(x_1) == a*x_1^2 + b*x_1 + c, ...
            df(x_0) == 2*a*x_0 + b, ...
            a, b, c);
      
      syms q(x)
      q(x) = simplify(a*x^2 + b*x + c);
      

      Obvi­ous­ly, the whole pur­pose of this oper­a­tion is to find an approx­i­ma­tion to the local min­i­miz­er of \(f'(x)\) . This gives


      \begin{align}
      0 &\overset{!}{=} q'(x_{min}) \\
      x_{min} &= -\frac{1}{2} \frac{x_0^2 f'(x_0) -x_1^2 f'(x_0) - 2 x_0 f(x_0) + 2 x_0 f(x_1)} {f(x_0) - f(x_1) - x_0 f'(x_0) + x_1 f'(x_0)}
      \end{align}

      We also would need to check the interpolant’s sec­ond deriv­a­tive \(q''(x_{min})\) to ensure the approx­i­mat­ed min­i­miz­er is indeed a min­i­mum of \(q(x)\) by requir­ing \(q''(x_{min}) > 0\) , with the sec­ond deriv­a­tive giv­en as:


      \begin{align}
      q''(x) &= - 2 \frac{f(x_0) - f(x_1) - x_0 f'(x_0) + x_1 f'(x_0)}{\left( x_0 - x_1 \right)^2 }
      \end{align}

      The premise of the line search in min­i­miza­tion prob­lems usu­al­ly is that the search direc­tion is already a direc­tion of descent. By hav­ing \(0 > f'(x_0)\) and \(f'(x_1) > 0\) (as would typ­i­cal­ly be the case when brack­et­ing the local min­i­miz­er of \(f(x)\) ), the inter­polant should always be (strict­ly) con­vex. If these con­di­tions do not hold, there might be no solu­tion at all: one obvi­ous­ly won’t be able to find a qua­drat­ic inter­polant giv­en the ini­tial con­di­tions for a func­tion that is lin­ear to machine pre­ci­sion. In that case, watch out for divi­sions by zero.

      Last but not least, if the objec­tive is to min­i­mize \(\varphi(\alpha) = f(\vec{x}_k + \alpha \vec{d}_k)\) using \(q(\alpha)\) , where \(\vec{d}_k\) is the search direc­tion and \(\vec{x}_k\) the cur­rent start­ing point, such that


      \begin{align}
      \varphi(0) &= f(\vec{x}_k) \\
      \varphi'(0) &= \nabla f(\vec{x}_k)' \vec{d}_k
      \end{align}

      then the above for­mu­las sim­pli­fy to


      \begin{align}
      a &= - \frac{\varphi(0) - \varphi(\alpha) + \alpha \varphi'(0)}{\alpha^2} \\
      b &= \frac{\alpha^2 \varphi'(\alpha)}{\alpha^2} \\
      c &= \frac{\alpha^2 \varphi(0)}{\alpha^2}
      \end{align}

      and, more impor­tant­ly, the local (approx­i­mat­ed) min­i­miz­er at \(\alpha_{min}\) sim­pli­fies to


      \begin{align}
      \alpha_{min} &= \frac{1}{2} \frac{\alpha^2 \varphi'(0)}{\varphi(0)-\varphi(\alpha)+\alpha\varphi'(0)}
      \end{align}

      If \(q(\alpha)\) is required to be strong­ly con­vex, then we’ll observe that


      \begin{align}
      q''(\alpha) &= 2a \overset{!}{\succeq} m
      \end{align}

      for an \(m > 0\) , giv­ing us that \(a\) must be greater than zero (or \(\epsilon\) , for that mat­ter), which is a triv­ial check. The fol­low­ing pic­ture visu­al­izes that this is indeed the case:

      Convexity of a parabola with respect to the highest-order coefficient.

      Con­vex­i­ty of a parabo­la for dif­fer­ent high­est-order coef­fi­cients a with pos­i­tive b (top), zero b (mid­dle) and neg­a­tive b (bot­tom). Low­est-order coef­fi­cient c is left out for brevi­ty.

      Juli 2nd, 2015 GMT +2 von
      Markus
      2015-07-2T04:54:49+02:00 2018-03-4T14:45:44+02:00 · 0 Kommentare
      Optimization Nonlinear Optimization Line Search Interpolation
      MATLAB Neural Networks
      • Note on programming

        I did alot of bird stuff today. I was really great out there. I just ... really LOVE being a bird.

        März 8th, 2015 GMT +2 von
        Markus
        2015-03-8T15:37:17+02:00 2015-03-8T15:37:17+02:00 · 0 Kommentare
        bird
        Humor
        • git: pushing to multiple remotes at the same time

          When work­ing on a project on GitHub, I some­times like to keep an addi­tion­al copy float­ing around on my own serv­er for eso­ter­i­cal rea­sons. While the fol­low­ing is pos­si­ble:

          $ git remote add origin git@a.b:c/d.git
          $ git remote add another git@w.x:y/z.git
          
          $ git push origin
          $ git push another
          

          it is quite annoy­ing to issue the push com­mand twice — advanced git-fu to the resuce. Some dude over at Stack Over­flow point­ed out that Git sup­ports the notion of a pushurl, being an end­point for push­ing to a giv­en remote. The fun thing is that every remote may have mul­ti­ple push URLs, which is exact­ly what I need­ed.

          It needs to be said that despite the usage of the --add flag in the fol­low­ing snip­pet, a push URL always over­writes the default URL, so adding only one URL results in the orig­i­nal entry being over­ruled. So, for the sit­u­a­tion giv­en in the exam­ple above:

          $ git remote add origin git@a.b:c/d.git
          $ git remote set-url --add --push origin git@a.b:c/d.git
          $ git remote set-url --add --push origin git@w.x:y/z.git
          
          $ git push origin
          

          And that’s it. By push­ing to origin Git instead push­es to both reg­is­tered URLs.

          Februar 22nd, 2015 GMT +2 von
          Markus
          2015-02-22T19:31:03+02:00 2015-03-4T15:17:35+02:00 · 0 Kommentare
          git
          Version Control
          • STM32F3-Discovery: no 72 MHz clock due to HSE never ready

            Now what a fun: Unboxed my brand new STM32F3-Dis­cov­ery, plugged it in — sweet blink­ing rap­ture. Com­piled my first demo pro­gram, played around with the timers, all was so good. Until I had a clos­er look at the sys­tem clock speed: 8 MHz it said. So I dug into the unknown grounds of STM32F3 devel­op­ment, end­ed up in the gen­er­at­ed firmware’s sys­tem ini­tial­iza­tion func­tion in system_stm32f30x.c — which looks like this:

            static void SetSysClock(void)
            {
                __IO uint32_t StartUpCounter = 0, HSEStatus = 0;
            
                /* SYSCLK, HCLK, PCLK2 and PCLK1 configuration -----------*/
                /* Enable HSE */
                RCC->CR |= ((uint32_t)RCC_CR_HSEON);
            
                /* Wait till HSE is ready and if Time out is reached exit */
                do
                {
                    HSEStatus = RCC->CR & RCC_CR_HSERDY;
                    StartUpCounter++;
                } while((HSEStatus == 0) && (StartUpCounter != HSE_STARTUP_TIMEOUT));
            
                if ((RCC->CR & RCC_CR_HSERDY) != RESET)
                {
                    HSEStatus = (uint32_t)0x01; // all good
                }
                else
                {
                    HSEStatus = (uint32_t)0x00; // nah.
                }
            
                /* ... */
            

            I did so, only to find out that HSEStatus nev­er switched to 0x01 because the RCC_CR_HSERDY flag was nev­er assert­ed in the first place.

            Obvi­ous­ly no one else in the whole wide web had trou­ble with this. Cold water? Let’s dive!
            Some dude at the ST forums point­ed me to the trick to out­put the RCC clock sig­nal to the board’s PA8 pin, which I did like so:

            void InitializeMCOGPIO() {
                RCC_AHBPeriphClockCmd(RCC_AHBPeriph_GPIOA, ENABLE);
            
                /* Configure MCO (PA8) */
                GPIO_InitTypeDef gpioStructure;
                gpioStructure.GPIO_Pin = GPIO_Pin_8;
                gpioStructure.GPIO_Speed = GPIO_Speed_50MHz;
                gpioStructure.GPIO_Mode = GPIO_Mode_AF;
                gpioStructure.GPIO_OType = GPIO_OType_PP;
                gpioStructure.GPIO_PuPd = GPIO_PuPd_NOPULL ;
                GPIO_Init(GPIOA, &gpioStructure);
            
                /* Output HSE clock on MCO pin (PA8) */
                RCC_MCOConfig(RCC_MCOSource_HSE);
            }
            

            Turned out … well, noth­ing. Flat­line on that pin. So I took my mul­ti­me­ter and went upstream from the oscil­la­tor pins. Sol­der bridge SB12, of course bridged, work­ing fine, SB17 open as request­ed, and then — silence on RB48. No beeps on my meter, no val­ue, just plain high imped­ance.

            To make a long sto­ry short: That 100 Ω resis­tor was borked, so I replaced it with some spare parts of an old scan­ner board I had float­ing around in the to-do stash. I’m not exact­ly known for mas­sive sol­der­ing expe­ri­ence, but this video helped a lot here.

            Final result:

            STM32F3-Discovery RB48 replaced

            Ugly but effec­tive. Works like a charm now.

            Februar 21st, 2015 GMT +2 von
            Markus
            2015-02-21T19:09:06+02:00 2015-02-21T19:09:06+02:00 · 0 Kommentare
            STM32F3 STM32F3-Discovery SMD soldering
            Embedded
            • Embedded CLion EAP: forcing arm-eabi-gcc onto cmake on Windows

              While CLion may become a good IDE for embed­ded devel­op­ment, it real­ly strug­gles with non con­for­mant build sce­nar­ios at the time being. As far as build­ing on Win­dows is con­cerned, you may either chose a MinGW- or cyg­win-based tool­chain and that’s it.

              CMake, how­ev­er, being the under­ly­ing build sys­tem, sup­ports the notion of exter­nal­ly defined tool­chains (-D CMAKE_TOOLCHAIN_FILE=...), which may be used to trick CLion into cross-com­pil­ing when it real­ly doesn’t want to.

              Note that this is mere­ly a hack to get you start­ing and by no means a full-fledged solu­tion. (Side note: Please share your insights.)

              As for my sys­tem, I final­ly went with MinGW (mingw-base 2013072200) as this solu­tion han­dles paths Win­dows-like, i.e. with­out cygwin’s /cygdrive/ man­gling; I also installed arm-none-eabi-gcc 4.9.2. Note also that installing the arm-gcc tool­chain with­in cyg­win might be an eas­i­er solu­tion in the long run.

              First, we cre­ate a tool­chain — in this case for a Cor­tex-M0+ — like fol­lows:

              include(CMakeForceCompiler)
              set(CMAKE_SYSTEM_NAME Generic)
              set(CMAKE_SYSTEM_PROCESSOR cortex-m0plus)
              
              find_program(ARM_CC arm-eabi-gcc
                  ${TOOLCHAIN_DIR}/bin
                  )
              find_program(ARM_CXX arm-eabi-g++
                  ${TOOLCHAIN_DIR}/bin
                  )
              find_program(ARM_OBJCOPY arm-eabi-objcopy
                  ${TOOLCHAIN_DIR}/bin
                  )
              find_program(ARM_SIZE_TOOL arm-eabi-size
                  ${TOOLCHAIN_DIR}/bin)
              
              CMAKE_FORCE_C_COMPILER(${ARM_CC} GNU)
              CMAKE_FORCE_CXX_COMPILER(${ARM_CXX} GNU)
              
              set(CMAKE_C_FLAGS
                "${CMAKE_C_FLAGS}"
                "-fno-common -ffunction-sections -fdata-sections"
              )
              
              if (CMAKE_SYSTEM_PROCESSOR STREQUAL "cortex-m0plus")
              
                set(CMAKE_C_FLAGS
                  "${CMAKE_C_FLAGS}"
                  "-mcpu=cortex-m0plus -mthumb"
                )
              
              else ()
                message(WARNING
                  "Processor not recognised in toolchain file, "
                  "compiler flags not configured."
                )
              endif ()
              
              # fix long strings (CMake appends semicolons)
              string(REGEX REPLACE ";" " " CMAKE_C_FLAGS "${CMAKE_C_FLAGS}")
              
              set(CMAKE_C_FLAGS "${CMAKE_C_FLAGS}" CACHE STRING "")
              
              set(BUILD_SHARED_LIBS OFF)
              

              In CLion’s Build, Execution, Deployment > CMake set­tings we then set the CMake Gen­er­a­tion options with

              -DTOOLCHAIN_DIR:PATH=c:/path/to/arm-eabi/ 
              -DCMAKE_TOOLCHAIN_FILE=toolchain-gcc-arm-eabi.cmake
              

              as can be seen in the fol­low­ing image.

              CLion CMake generation options

              If we weren’t using MinGW but cyg­win, CMake would be unable to find the exe­cuta­bles giv­en a MinGW-style path (e.g. c:/some/thing); a cyg­win-style path (e.g. /cygdrive/c/some/thing) would then have to be used here. How­ev­er, when the cyg­win tool­chain is select­ed in CLion, all source file paths are also pre­sent­ed cyg­win-style, which obvi­ous­ly can’t be accessed from a non-cyg­win appli­ca­tion. Long sto­ry short: Know your tools, I didn’t.

              Using Help > Show Generated CMake Files in Explorer you can see the gen­er­at­ed project files.

              CLion Show Generated Files

              Delet­ing this fold­er forces a full inval­i­da­tion of CMake’s gen­er­at­ed cache, which might oth­er­wise not hap­pen.

              CLion Generated Files in Explorer

              After­wards you can trig­ger a regen­er­a­tion of the cache by using the Reload CMake Project but­ton in the CMake Prob­lem pane.

              CLion regenerate CMake project

              Now the CMake Cache should show the cor­rect paths.

              CLion CMake cache

              If you then build your project, CMake will use the cross­com­pil­er and place the bina­ries in the fold­er you delet­ed ear­li­er.

              Februar 12th, 2015 GMT +2 von
              Markus
              2015-02-12T06:21:21+02:00 2015-07-3T11:34:09+02:00 · 6 Kommentare
              Windows IDE CLion MinGW cygwin
              Allgemein Embedded
    1. « newer
    2. 1
    3. 2
    4. 3
    5. 4
    6. 5
    7. 6
    8. 7
    9. 8
    10. 9
    11. older »
    • Kategorien

      • .NET
        • ASP.NET
        • Core
        • DNX
      • Allgemein
      • Android
      • Data Science
      • Embedded
      • FPGA
      • Humor
      • Image Processing
      • Kalman Filter
      • Machine Learning
        • Caffe
        • Hidden Markov Models
        • ML Summarized
        • Neural Networks
        • TensorFlow
      • Mapping
      • MATLAB
      • Robotik
      • Rust
      • Signal Processing
      • Tutorial
      • Version Control
    • Neueste Beiträge

      • Summarized: The E-Dimension — Why Machine Learning Doesn’t Work Well for Some Problems?
      • Use your conda environment in Jupyter Notebooks
      • Building OpenCV for Anaconda Python 3
      • Using TensorFlow’s Supervisor with TensorBoard summary groups
      • Getting an image into and out of TensorFlow
    • Kategorien

      .NET Allgemein Android ASP.NET Caffe Core Data Science DNX Embedded FPGA Hidden Markov Models Humor Image Processing Kalman Filter Machine Learning Mapping MATLAB ML Summarized Neural Networks Robotik Rust Signal Processing TensorFlow Tutorial Version Control
    • Tags

      .NET Accelerometer Anaconda Bitmap Bug Canvas CLR docker FPGA FRDM-KL25Z FRDM-KL26Z Freescale git Gyroscope Integration Drift Intent J-Link Linear Programming Linux Magnetometer Matlab Mono Naismith OpenCV Open Intents OpenSDA Optimization Pipistrello Player/Stage PWM Python Sensor Fusion Simulink Spartan 6 svn tensorflow Tilt Compensation TRIAD ubuntu Windows Xilinx Xilinx SDK ZedBoard ZYBO Zynq
    • Letzte Kommetare

      • Lecke Mio bei Frequency-variable PWM generator in Simulink
      • Vaibhav bei Use your conda environment in Jupyter Notebooks
      • newbee bei Frequency-variable PWM generator in Simulink
      • Markus bei Using TensorFlow’s Supervisor with TensorBoard summary groups
      • Toke bei Using TensorFlow’s Supervisor with TensorBoard summary groups
    • Blog durchsuchen

    • August 2022
      M D M D F S S
      « Mrz    
      1234567
      891011121314
      15161718192021
      22232425262728
      293031  
    • Self

      • Find me on GitHub
      • Google+
      • Me on Stack­Ex­change
      • Ye olde blog
    • Meta

      • Anmelden
      • Beitrags-Feed (RSS)
      • Kommentare als RSS
      • WordPress.org
    (Generiert in 0,344 Sekunden)

    Zurück nach oben.